Problema del diámetro de grados

En teoría de grafos , el problema del diámetro de grado consiste en encontrar el grafo G más grande posible (en términos del tamaño de su conjunto de vértices V ) de diámetro k tal que el grado máximo de cualquiera de los vértices en G sea como máximo d . El tamaño de G está acotado superiormente por la cota de Moore ; para 1 < k y 2 < d , solo el grafo de Petersen , el grafo de Hoffman-Singleton y posiblemente grafos (aún no probados) de diámetro k = 2 y grado d = 57 alcanzan la cota de Moore. En general, los grafos de mayor diámetro de grado son mucho más pequeños que la cota de Moore.

Dejar${\displaystyle n_{d,k}}$Sea el número máximo posible de vértices para un grafo con grado como máximo d y diámetro k . Entonces${\displaystyle n_{d,k}\leq M_{d,k}}$, dónde${\displaystyle M_{d,k}}$es el límite de Moore :

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

Este límite se alcanza para muy pocos grafos, por lo que el estudio se centra en cuán cerca existen grafos del límite de Moore. Para el comportamiento asintótico, tenga en cuenta que${\displaystyle M_{d,k}=d^{k}+O(d^{k-1})}$.

Defina el parámetro${\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}}$Se conjetura que${\displaystyle \mu _{k}=1}$para todo k . Se sabe que${\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1}$y eso${\displaystyle \mu _{4}\geq 1/4}$.

• Jaula (teoría de grafos)
• Tabla de los gráficos más grandes conocidos de un diámetro y grado máximo dados
• Tabla de digrafos de diámetro de grado simétricos en vértices
• Problema del subgrafo con grado y diámetro máximos acotados