Gráfico de Moore
En teoría de grafos , un gráfico de Moore es un gráfico regular de grado d y diámetro k cuyo número de vértices es igual al límite superior
Una definición equivalente de un gráfico de Moore es que es un gráfico de diámetro con circunferencia . Otra definición equivalente de un grafo de Moore es que tiene circunferencia y precisamente ciclos de longitud , donde y son, respectivamente, los números de vértices y aristas de . De hecho, son extremos con respecto al número de ciclos cuya longitud es la circunferencia del gráfico. [1]
Los gráficos de Moore fueron nombrados por Hoffman & Singleton (1960) en honor a Edward F. Moore , quien planteó la cuestión de describir y clasificar estos gráficos.
Además de tener el máximo número posible de vértices para una combinación determinada de grado y diámetro, los gráficos de Moore tienen el mínimo número posible de vértices para un gráfico regular con un grado y una circunferencia determinados. Es decir, cualquier gráfico de Moore es una jaula . [2] La fórmula para el número de vértices en un gráfico de Moore se puede generalizar para permitir una definición de gráficos de Moore con circunferencias pares y circunferencias impares, y nuevamente estos gráficos son jaulas.
Sea G cualquier gráfico con grado máximo d y diámetro k , y considere el árbol formado por la búsqueda primero en anchura a partir de cualquier vértice v . Este árbol tiene 1 vértice en el nivel 0 ( v mismo), y como máximo d vértices en el nivel 1 (los vecinos de v ). En el siguiente nivel, hay como máximo d ( d − 1) vértices: cada vecino de v usa una de sus adyacencias para conectarse a v y, por lo tanto, puede tener como máximo d − 1 vecinos en el nivel 2. En general, un argumento similar muestra que en cualquier nivel 1 ≤ i ≤k , puede haber como máximo d ( d − 1) i −1 vértices. Por lo tanto, el número total de vértices puede ser como máximo
Hoffman y Singleton (1960) definieron originalmente un grafo de Moore como un grafo en el que este límite en el número de vértices se cumple exactamente. Por lo tanto, cualquier gráfico de Moore tiene el máximo número de vértices posibles entre todos los gráficos con máximo grado d y diámetro k .
