Problema de diámetro en grados

En teoría de grafos , el problema de grados de diámetro 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 <  ky 2 <  d solo el gráfico de Petersen , el gráfico de Hoffman-Singleton y posiblemente un gráfico más (aún no probado que exista) de diámetro k = 2 y grado d  = 57 alcanzan el límite de Moore. En general, los gráficos de mayor diámetro en grados son mucho más pequeños que el límite de Moore.

Fórmula

Sea el número máximo posible de vértices para una gráfica con grado como máximo d y diámetro k . Entonces , ¿dónde está 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 gráficos, por lo que el estudio se mueve a qué tan cerca existen los gráficos del límite de Moore. Para el comportamiento asintótico, tenga en cuenta eso .${\displaystyle M_{d,k}=d^{k}+O(d^{k-1})}$

Defina el parámetro . Se conjetura que para todo k . Se sabe eso y aquello .${\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}$

Ver también

• Jaula (teoría de grafos)
• Tabla de gráficos de diámetro en grados
• Tabla de dígrafos de diámetro de grado simétrico de vértice
• Problema de subgrafo limitado por grados y diámetros máximos

Referencias

• Bannai, E .; Ito, T. (1973), "Sobre gráficos de Moore", J. Fac. Sci. Univ. Tokio 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 hay un gráfico de Moore irregular", American Mathematical Monthly , Mathematical Association of America, 75 (1): 42–43, doi : 10.2307 / 2315106 , JSTOR  2315106 , MR  0225679

• Miller, Mirka ; Širáň, Jozef (2005), "Gráficos de Moore y más allá: una encuesta del problema de grado / diámetro" , Revista Electrónica de Combinatoria , Encuesta dinámica: DS14

• CombinatoricsWiki - El problema del grado / diámetro