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

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

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

Формула

Пусть ${\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}$^[3]. Есть гипотеза, что для степеней ${\displaystyle d\geqslant 6}$ не существует ${\displaystyle (d,2)}$-графов с дефектом 2. О графах с дефектом, большим 2, известно мало^[4].

Для асимптотического поведения заметим, что ${\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-трудной.