Problema de diámetro en grados

Encontrar el gráfico más grande del diámetro y grado dados

En teoría de grafos , el problema del diámetro de grado es el problema de 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ás grande de cualquiera de los vértices en G sea como máximo d . El tamaño de G está acotado arriba por el límite de Moore ; para 1 < k y 2 < d , solo el grafo de Petersen , el grafo de Hoffman-Singleton y posiblemente grafos (aún no se ha demostrado que existan) de diámetro k = 2 y grado d = 57 alcanzan el límite de Moore. En general, los grafos de grado-diámetro más grandes son mucho más pequeños en tamaño que el límite de Moore.

Fórmula

Sea el número máximo posible de vértices para un grafo con grado como máximo d y diámetro k . Entonces , donde es el límite de Moore : ${\displaystyle n_{d,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}}&{\text{ if }}d>2\\2k+1&{\text{ if }}d=2\end{cases}}}$

Este límite se alcanza para muy pocos grafos, por lo que el estudio se centra en qué tan cerca están los 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 . Se conjetura que para todo k . Se sabe que y que . ${\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}}$ ${\displaystyle \mu _{k}=1}$ ${\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1}$ ${\displaystyle \mu _{4}\geq 1/4}$

Véase también

• Jaula (teoría de grafos)
• Tabla de los mayores gráficos conocidos de un diámetro y grado máximo dados
• Tabla de dígrafos de diámetro de grado simétricos con vértices
• Problema de subgrafos con máximo grado y diámetro acotados

Referencias

• Bannai, E.; Ito, T. (1973), "Sobre los grafos de Moore", J. Fac. Sci. Univ. Tokyo Ser. A , 20 : 191–208, MR  0323615
• Hoffman, Alan J. ; Singleton, Robert R. (1960), "Gráficos de Moore con diámetro 2 y 3" (PDF) , IBM Journal of Research and Development , 5 (4): 497–504, doi :10.1147/rd.45.0497, MR  0140437
• Singleton, Robert R. (1968), "No existe ningún gráfico de Moore irregular", American Mathematical Monthly , 75 (1), Mathematical Association of America: 42–43, doi :10.2307/2315106, JSTOR  2315106, MR  0225679
• Miller, Mirka ; Širáň, Jozef (2005), "Gráficos de Moore y más allá: un estudio del problema de grado/diámetro", Revista electrónica de combinatoria , Estudio dinámico: DS14
• CombinatoricsWiki - El problema del grado/diámetro