¿Existe una gráfica de Moore con circunferencia 5 y grado 57?
En teoría de grafos , un grafo de Moore es un grafo 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 gráfico de Moore es que tiene circunferencia y precisamente ciclos de duración , dónde y son, respectivamente, el número 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 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 número máximo posible de vértices para una combinación dada de grado y diámetro, los gráficos de Moore tienen el número mínimo posible de vértices para un gráfico regular con un grado y circunferencia dados. 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 los gráficos de Moore con circunferencia par y circunferencia impar, y nuevamente estos gráficos son jaulas.
Delimitación de vértices por grado y diámetro
Sea G cualquier gráfico con grado máximo d y diámetro k , y considere el árbol formado por la búsqueda de amplitud primero comenzando desde cualquier vértice v . Este árbol tiene 1 vértice en el nivel 0 ( v en sí 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 av 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) originalmente definieron un grafo de Moore como un grafo para el cual este límite en el número de vértices se cumple exactamente. Por lo tanto, cualquier gráfico de Moore tiene el número máximo de vértices posible entre todos los gráficos con grado máximo d y diámetro k .
Más tarde, Singleton (1968) mostró que las gráficas de Moore pueden definirse de manera equivalente como de diámetro ky circunferencia 2 k +1; estos dos requisitos se combinan para forzar que la gráfica sea d -regular durante algún d y para satisfacer la fórmula de conteo de vértices.
Gráficos de Moore como jaulas
En lugar de limitar por arriba el número de vértices en un gráfico en términos de su grado máximo y su diámetro, podemos calcular mediante métodos similares un límite inferior en el número de vértices en términos de su grado mínimo y su circunferencia . [2] Suponga que G tiene un grado d mínimo y una circunferencia de 2 k +1. Elija arbitrariamente un vértice inicial v y, como antes, considere el árbol de búsqueda de ancho primero 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 dos vértices en el nivel 1 no pueden ser adyacentes entre sí o con un vértice compartido en el nivel 2 porque eso crearía un ciclo más corto que la circunferencia supuesta. 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 gráfico de Moore, este límite en el número de vértices se cumple exactamente. Cada gráfico de Moore tiene una circunferencia exactamente 2 k +1: no tiene suficientes vértices para tener una circunferencia mayor, y un ciclo más corto provocaría que haya muy pocos vértices en los primeros k niveles de algún primer árbol de búsqueda de amplitud. Por lo tanto, cualquier gráfico de Moore tiene el número mínimo de vértices posible entre todos los gráficos con grado d mínimo y diámetro k : es una jaula .
Para una circunferencia uniforme de 2 k , se puede formar de manera similar un árbol de búsqueda de ancho primero a partir del punto medio de un solo borde. El límite resultante en el número mínimo de vértices en una gráfica de esta circunferencia con grado mínimo d es
(El lado derecho de la fórmula, en cambio, cuenta el número de vértices en un primer árbol de búsqueda de amplitud a partir de un solo vértice, lo que representa 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, las gráficas de Moore a veces se definen como que incluyen las gráficas que cumplen exactamente con este límite. Nuevamente, cualquier gráfico de este tipo debe ser una jaula.
Ejemplos de
El teorema de Hoffman-Singleton establece que cualquier gráfico de Moore con circunferencia 5 debe tener grados 2, 3, 7 o 57. Los gráficos de Moore son: [3]
- Las gráficas completas en n> 2 nodos (diámetro 1, circunferencia 3, grado n-1, orden n)
- Los ciclos impares (diámetro n, circunferencia 2n + 1, grado 2, orden 2n + 1)
- El gráfico de Petersen (diámetro 2, circunferencia 5, grado 3, orden 10)
- El gráfico de Hoffman-Singleton (diámetro 2, circunferencia 5, grado 7, orden 50)
- Una gráfica hipotética de diámetro 2, circunferencia 5, grado 57 y orden 3250, cuya existencia se desconoce [4]
Aunque todos los gráficos de Moore conocidos son gráficos transitivos de vértice , el desconocido (si existe) no puede ser transitivo de vértice, ya que su grupo de automorfismos puede tener un orden de 375 como máximo, menos que su número de vértices. [5]
Si se utiliza la definición generalizada de gráficos de Moore que permite gráficos de circunferencia pares, los gráficos de Moore de circunferencia par corresponden a gráficos de incidencia de polígonos generalizados (posiblemente degenerados) . Algunos ejemplos son los ciclos pares., los gráficos bipartitos completos con circunferencia cuatro, el gráfico de Heawood con grado 3 y circunferencia 6, y el gráfico de Tutte-Coxeter con grado 3 y circunferencia 8. De manera más general, se sabe que, además de las gráficas enumeradas anteriormente, todas las gráficas de Moore deben tener circunferencia 5, 6, 8 o 12. [6] El caso de circunferencia par también se sigue del teorema de Feit-Higman sobre los posibles valores de n para un n-gon generalizado.
Ver también
Notas
- ^ Azarija y Klavžar (2015) .
- ↑ a b Erdős, Rényi y Sós (1966) .
- ^ Bollobás (1998) , Teorema 19, p. 276.
- ↑ Dalfó (2019) .
- ^ Mačaj y Širáň (2010) .
- ^ Bannai e Ito (1973) ; Damerell (1973)
Referencias
- Azarija, Jernej; Klavžar, Sandi (2015), "Los ciclos y gráficos de Moore son gráficos extremos para ciclos convexos", Journal of Graph Theory , 80 : 34–42, arXiv : 1210.6342 , doi : 10.1002 / jgt.21837
- Bannai, E .; Ito, T. (1973), "Sobre gráficos finitos de Moore" , Revista de la Facultad de Ciencias de la Universidad de Tokio. Secta. 1 A, Mathematics , 20 : 191-208, MR 0323615 , archivado desde el original el 24 de abril de 2012
- Bollobás, Béla (1998), Teoría Moderna de Grafos , Textos de Posgrado en Matemáticas , 184 , Springer-Verlag.
- Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF) , Álgebra lineal y sus aplicaciones , 569 : 1–14, doi : 10.1016 / j.laa.2018.12.035 , hdl : 2117/127212 , MR 3901732
- Damerell, RM (1973), "On Moore graphs", Mathematical Proceedings of the Cambridge Philosophical Society , 74 (2): 227-236, Bibcode : 1973PCPS ... 74..227D , doi : 10.1017 / S0305004100048015 , MR 0318004
- Erdős, Paul ; Rényi, Alfréd ; Sós, Vera T. (1966), "Sobre un problema de teoría de grafos" (PDF) , Studia Sci. Matemáticas. Hungar. , 1 : 215-235, Archivado desde el original (PDF) en 09/03/2016 , obtenidos 2010-02-23.
- Hoffman, Alan J .; Singleton, Robert R. (1960), "Gráficos de Moore con diámetro 2 y 3", IBM Journal of Research and Development , 5 (4): 497–504, doi : 10.1147 / rd.45.0497 , MR 0140437
- Mačaj, Martin; Širáň, Jozef (2010), "Búsqueda de propiedades del gráfico de Moore faltante", Álgebra lineal y sus aplicaciones , 432 (9): 2381-2398, doi : 10.1016 / j.laa.2009.07.018.
- Singleton, Robert R. (1968), "No hay un gráfico de Moore irregular", American Mathematical Monthly , 75 (1): 42–43, doi : 10.2307 / 2315106 , JSTOR 2315106 , MR 0225679
enlaces externos
- Brouwer y Haemers: espectros de gráficos
- Eric W. Weisstein , Moore Graph ( Teorema de Hoffman-Singleton ) en MathWorld .