Задача степеня — діаметра

Зада́ча сте́пеня — діа́метра — задача пошуку найбільшого можливого графа ${\displaystyle G}$ (в термінах розміру множини його вершин ${\displaystyle V}$) діаметром ${\displaystyle k}$ такого, що найбільший степінь будь-якої вершини в графі ${\displaystyle G}$ не перевищує ${\displaystyle d}$. Розмір графа ${\displaystyle G}$ обмежений зверху межею Мура. Для ${\displaystyle 1<k}$ і ${\displaystyle 2<d}$ тільки граф Петерсена, граф Гофмана — Синглтона і, можливо, граф із діаметром ${\displaystyle k=2}$ і степенем ${\displaystyle d=57}$ досягають межі Мура. В загальному випадку графи з найбільшими значеннями степінь/діаметр мають розмір, значно менший від межі Мура.

Вивчається також задача пошуку найбільшого можливого орграфа, замість степеня графа в цьому випадку використовують напівстепень виходу.

Формула

Нехай ${\displaystyle n_{d,k}}$ — найбільше можливе число вершин графа зі степенем, що не перевершує ${\displaystyle d}$, і діаметром ${\displaystyle k}$, тоді ${\displaystyle n_{d,k}\leq M_{d,k}}$, де ${\displaystyle M_{d,k}}$ — межа Мура:

${\displaystyle M_{d,k}={\begin{cases}1+d{\frac {(d-1)^{k}-1}{d-2}}&d\geqslant 2\\2k+1&d=2\end{cases}}}$

Ця межа досягається в рідкісних випадках, тому вивчення пішло в напрямку, наскільки близькі до межі Мура існують графи.

Величину ${\displaystyle \delta =M_{d,k}-|V|}$ називають дефектом графа (тут ${\displaystyle |V|}$ — число вершин у графі). Кажуть, що граф має малий дефект, якщо ${\displaystyle \delta \leqslant d}$. Є гіпотеза, що для степенів ${\displaystyle d\geqslant 6}$ не існує ${\displaystyle (d,2)}$-графів із дефектом 2. Про графи з дефектом, більшим від 2, відомо мало.

Для асимптотичної поведінки зауважимо, що ${\displaystyle M_{d,k}=d^{k}+O(d^{k-1})}$.

Для параметра ${\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}}$ висловлено гіпотезу, що ${\displaystyle \mu _{k}=1}$ для всіх ${\displaystyle k}$; відомо, що ${\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1}$ і що ${\displaystyle \mu _{4}\geq 1/4}$.

MaxDDBS

Якщо дано зв'язний граф-господар^[] ${\displaystyle G}$, верхня межа степеня ${\displaystyle d}$ і верхня межа діаметра ${\displaystyle k}$, шукається найбільший підграф ${\displaystyle S}$ графа ${\displaystyle G}$ з найбільшим степенем, що не перевершує ${\displaystyle d}$ і діаметром, що не перевершує ${\displaystyle k}$. Цю задачу називають MaxDDBS, і вона містить задачу розміру — діаметра як частковий випадок (а саме, якщо за граф-господар взяти досить великий повний граф). Задача є NP-складною.

Див. також

• Клітка (теорія графів)

Примітки

1. Молодцов, 2004, с. 109.
2. Miller, 2010, с. 341.
3. Miller, 2010, с. 337.
4. Miller, 2010, с. 338.

Література

• Молодцов С. Г. Наибольшие графы диаметра 2 и степени 6 // Дискретный анализ и исследование операций : тезисы докладов. — Новосибирск, Академгородок : Институт математики им. С.Л. Соболева СО РАН, 2004. — Вип. 28 июня - 2 июля 2004 (27 червня). — С. 109. з джерела 10 квітня 2022. Процитовано 16 березня 2022.
• Bannai E., Ito T. On Moore graphs // J. Fac. Sci. Univ. Tokyo Ser. A. — 1973. — Т. 20 (27 червня). — С. 191–208.
• Hoffman Alan J., Singleton Robert R. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. — 1960. — Т. 5, вип. 4 (27 червня). — С. 497–504. — DOI:10.1147/rd.45.0497. з джерела 18 травня 2008. Процитовано 16 березня 2022.
• Singleton Robert R. There is no irregular Moore graph // American Mathematical Monthly. — Mathematical Association of America, 1968. — Т. 75, вип. 1 (27 червня). — С. 42–43. — DOI:10.2307/2315106.
• Miller Mirka, Širáň Jozef. Moore graphs and beyond: A survey of the degree/diameter problem // . — 2005. — Т. Dynamic survey (27 червня). — С. DS14. з джерела 10 лютого 2022. Процитовано 16 березня 2022.
• . Архів оригіналу за 20 лютого 2012. Процитовано 16 березня 2022.
• Miller Mirka. An Overview of the Degree/Diameter Problem for Directed, Undirected and Mixed Graphs // Extended abstracts of IWONT. — Barcelona, 2010, 2010. — 27 червня. — С. 335—346.
• Dekker A., Perez-Roses H., Pineda-Villavicencio G., Watters P. The Maximum Degree & Diameter-Bounded Subgraph and its Applications // Journal of Mathematical Modelling and Algorithms. — 2012. — 27 червня. — DOI:10.1007/s10852-012-9182-8.
• Miller M., Perez-Roses H., Ryan J. The Maximum Degree and Diameter Bounded Subgraph in the Mesh. Discrete Applied Mathematics. — 2012. — 27 червня. — DOI:10.1016/j.dam.2012.03.035.