Проблема с диаметром градусов

В теории графов проблема диаметра степени — это проблема поиска максимально возможного графа $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}}&{\text{ if }}d>2\\2k+1&{\text{ if }}d=2\end{cases}}

Эта граница достигается для очень небольшого числа графов, поэтому исследование переходит к вопросу о том, насколько близки существуют графы к границе Мура.Для асимптотического поведения отметим, что $M_{d,k}=d^{k}+O(d^{k-1})$ .

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