Проблема размера — диаметра

Проблема размера — диаметра — задача поиска наибольшего возможного графа $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
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья