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

Проблема размера — диаметра — задача поиска наибольшего возможного графа $G$ (в терминах размера множества его вершин $V$) диаметра $k$ такого, что наибольшая степень любой вершины в графе $G$ не превосходит $d$. Размер графа $G$ ограничен сверху границей Мура. Для $1<k$ и $2<d$ только граф Петерсена, граф Хоффмана — Синглтона и, возможно, граф с диаметром $k=2$ и степенью $d=57$ достигают границу Мура. В общем случае наибольшие графы со значениями степень/диаметр имеют размер, много меньший границы Мура.

Изучается также задача поиска наибольшего возможного орграфа, вместо степени графа в этом случае используется полустепень исхода.

Формула

Пусть $n_{d,k}$ — максимально возможное число вершин графа со степенью, не превосходящей $d$, и диаметром $k$, тогда $n_{d,k}\leq M_{d,k}$, где $M_{d,k}$ является границей Мура:

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

Эта граница достигается в очень редких случаях, так что изучение пошло в направлении, насколько близко существуют графы к границе Мура.

Величина $\delta =M_{d,k}-|V|$ называется дефектом графа (здесь $|V|$ — число вершин в графе). Говорят, что граф имеет малый дефект, если $\delta \leqslant d$. Есть гипотеза, что для степеней $d\geqslant 6$ не существует $(d,2)$-графов с дефектом 2. О графах с дефектом, большим 2, известно мало.

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

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

MaxDDBS

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

Литература

• Молодцов С. Г. Наибольшие графы диаметра 2 и степени 6 // Дискретный анализ и исследование операций : Тезисы докладов. — Новосибирск, Академгородок: Институт математики им. С.Л. Соболева СО РАН, 2004. — Вып. 28 июня - 2 июля 2004. — С. 109.
• Bannai E., Ito T. On Moore graphs // J. Fac. Sci. Univ. Tokyo Ser. A. — 1973. — Т. 20. — С. 191–208.
• Hoffman Alan J., Singleton Robert R. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. — 1960. — Т. 5, вып. 4. — С. 497–504. — doi:10.1147/rd.45.0497.
• Singleton Robert R. There is no irregular Moore graph // American Mathematical Monthly. — 1968. — Т. 75, вып. 1. — С. 42–43. — doi:10.2307/2315106. — .
• Miller Mirka, Širáň Jozef. Moore graphs and beyond: A survey of the degree/diameter problem // Electronic Journal of Combinatorics. — 2005. — Т. Dynamic survey. — С. DS14.
• CombinatoricsWiki - The Degree/Diameter Problem  (неопр.).
• Miller Mirka. An Overview of the Degree/Diameter Problem for Directed, Undirected and Mixed Graphs // Extended abstracts of IWONT. — Barcelona, 2010, 2010. — С. 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. — 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. — doi:10.1016/j.dam.2012.03.035.