En teoría de grafos , un grafo de Moore es un grafo regular cuya circunferencia (la longitud del ciclo más corto ) es más del doble de su diámetro (la distancia entre los dos vértices más alejados ). Si el grado de dicho grafo es d y su diámetro es k , su circunferencia debe ser igual a 2 k + 1. Esto es cierto, para un grafo de grado d y diámetro k , si y solo si su número de vértices es igual a
un límite superior para el mayor número posible de vértices en cualquier grafo con este grado y diámetro. Por lo tanto, estos grafos resuelven el problema del diámetro del grado para sus parámetros.
Otra definición equivalente de un grafo de Moore G es que tiene circunferencia g = 2 k + 1 y precisamente norte/gramo ( m – n + 1) ciclos de longitud g , donde n y m son, respectivamente, los números de vértices y aristas de G . De hecho, son extremales con respecto al número de ciclos cuya longitud es la circunferencia del grafo. [1]
Los gráficos de Moore fueron nombrados por Hoffman y 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 dada de grado y diámetro, los grafos de Moore tienen el mínimo número posible de vértices para un grafo regular con grado y circunferencia dados. Es decir, cualquier grafo de Moore es una jaula . [2] La fórmula para el número de vértices en un grafo de Moore se puede generalizar para permitir una definición de grafos de Moore con circunferencia par así como con circunferencia impar, y nuevamente estos grafos son jaulas.
Sea G cualquier grafo con grado máximo d y diámetro k , y considérese el árbol formado por búsqueda en amplitud comenzando desde 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 para el cual se cumple exactamente este límite en el número de vértices. Por lo tanto, cualquier grafo de Moore tiene el número máximo de vértices posible entre todos los grafos con el máximo grado d y diámetro k .
Más tarde, Singleton (1968) demostró que los grafos de Moore pueden definirse de manera equivalente como aquellos que tienen un diámetro k y una circunferencia 2 k + 1 ; estos dos requisitos se combinan para forzar al grafo a ser d -regular para algún d y a satisfacer la fórmula de conteo de vértices.
En lugar de limitar superiormente el número de vértices en un grafo en términos de su grado máximo y su diámetro, podemos calcular mediante métodos similares un límite inferior para el número de vértices en términos de su grado mínimo y su circunferencia. [2] Supongamos que G tiene un grado mínimo d y una circunferencia 2 k + 1 . Elija arbitrariamente un vértice inicial v , y como antes considere el árbol de búsqueda en amplitud con raíz en v . Este árbol debe tener un vértice en el nivel 0 ( v en sí mismo), y al menos d vértices en el nivel 1. En el nivel 2 (para k > 1 ), debe haber al menos d ( d − 1) vértices, porque cada vértice en el nivel 1 tiene al menos d − 1 adyacencias restantes para llenar, y no pueden haber dos vértices en el nivel 1 adyacentes entre sí o a un vértice compartido en el nivel 2 porque eso crearía un ciclo más corto que la circunferencia asumida. En general, un argumento similar muestra que en cualquier nivel 1 ≤ i ≤ k , debe haber al menos d ( d − 1) i vértices. Por lo tanto, el número total de vértices debe ser al menos
En un grafo de Moore, este límite en el número de vértices se cumple exactamente. Cada grafo de Moore tiene una circunferencia exactamente de 2 k + 1 : no tiene suficientes vértices para tener una circunferencia mayor, y un ciclo más corto provocaría que hubiera muy pocos vértices en los primeros k niveles de algún árbol de búsqueda en amplitud. Por lo tanto, cualquier grafo de Moore tiene la cantidad mínima de vértices posible entre todos los grafos con un grado mínimo d y una circunferencia de 2 k + 1 : es una jaula.
Para una circunferencia par de 2 k , se puede formar de manera similar un árbol de búsqueda en anchura comenzando desde el punto medio de una única arista. El límite resultante en el número mínimo de vértices en un grafo de esta circunferencia con un grado mínimo d es
(El lado derecho de la fórmula cuenta, en cambio, el número de vértices de un árbol de búsqueda en amplitud que comienza desde un único vértice, lo que tiene en cuenta la posibilidad de que un vértice en el último nivel del árbol pueda ser adyacente a d vértices en el nivel anterior). Por lo tanto, los gráficos de Moore a veces se definen como aquellos que cumplen exactamente con este límite. Nuevamente, cualquier gráfico de este tipo debe ser una jaula.
El teorema de Hoffman-Singleton establece que cualquier grafo de Moore con circunferencia 5 debe tener grado 2, 3, 7 o 57. Los grafos de Moore son: [3]
Aunque todos los grafos de Moore conocidos son grafos transitivos de vértices , el desconocido (si existe) no puede ser transitivo de vértices, ya que su grupo de automorfismos puede tener un orden de como máximo 375, menor que su número de vértices. [5]
Si se utiliza la definición generalizada de los grafos de Moore que permite grafos de circunferencia par, los grafos de Moore de circunferencia par corresponden a grafos de incidencia de polígonos generalizados (posiblemente degenerados) . Algunos ejemplos son los ciclos pares C 2 n , los grafos bipartitos completos K n , n con circunferencia cuatro, el grafo de Heawood con grado 3 y circunferencia 6, y el grafo de Tutte–Coxeter con grado 3 y circunferencia 8. De manera más general, se sabe que, aparte de los grafos enumerados anteriormente, todos los grafos de Moore deben tener circunferencia 5, 6, 8 o 12. [6] El caso de circunferencia par también se deduce del teorema de Feit-Higman sobre los posibles valores de n para un n -gono generalizado.
