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

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

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

Формула

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

$M_{d,k}=\{\begin{array}{cc}1+d\frac{(d-1{)}^k-1}{d-2}& d⩾2\\ 2k+1& d=2\end{array}$

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

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

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

Для параметра ${\mu }_k=\underset{d\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{n_{d,k}}{d^k}$ висловлено гіпотезу, що ${\mu }_k=1$ для всіх $k$; відомо, що ${\mu }_1={\mu }_2={\mu }_3={\mu }_5=1$ і що ${\mu }_4\ge 1/4$.

MaxDDBS

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

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Cite web
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття