gráfico de moore

Gráfico regular con circunferencia mayor que el doble de su diámetro

Problema no resuelto en matemáticas :

¿Existe una gráfica de Moore con circunferencia 5 y grado 57?

(más problemas sin resolver en matemáticas)

En teoría de grafos , un gráfico de Moore es un gráfico 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 dicha gráfica es d y su diámetro es k , su circunferencia debe ser igual a 2 k + 1 . Esto es cierto, para una gráfica de grado d y diámetro k , si y sólo si su número de vértices es igual

${\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i},}$

un límite superior en el mayor número posible de vértices en cualquier gráfico con este grado y diámetro. Por lo tanto, estas gráficas resuelven el problema de grados de diámetro para sus parámetros.

Otra definición equivalente de un gráfico de Moore G es que tiene circunferencia g = 2 k + 1 y precisamentenorte/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 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 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 circunferencia par y circunferencia impar, y nuevamente estos gráficos son jaulas.

Delimitar vértices por grado y diámetro.

El gráfico de Petersen como un gráfico de Moore. Cualquier primer árbol de búsqueda de amplitud tiene d ( d − 1) ^{i −1} vértices en su i -ésimo nivel para i ≥ 1 .

Sea G cualquier gráfico con grado máximo d y diámetro k , y considere el árbol formado por la primera búsqueda en amplitud 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

${\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i}.}$

Hoffman y Singleton (1960) definieron originalmente un gráfico de Moore como un gráfico 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 posible entre todos los gráficos con grado máximo d y diámetro k .

Más tarde, Singleton (1968) demostró que las gráficas de Moore pueden definirse de manera equivalente como si tuvieran un diámetro k y una circunferencia 2 k + 1 ; Estos dos requisitos se combinan para forzar que el gráfico sea d -regular para algún d y para satisfacer la fórmula de conteo de vértices.

Moore grafica como jaulas

En lugar de limitar el número de vértices de 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 del 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 de 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 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 hay dos vértices en el nivel 1 que puedan 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) ⁱ vértices. Por lo tanto, el número total de vértices debe ser al menos

${\displaystyle 1+d\sum _{i=1}^{k-1}(d-1)^{i}.}$

En un gráfico de Moore, este límite del 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 más alta, y un ciclo más corto causaría que haya muy pocos vértices en los primeros k niveles de algún árbol de búsqueda de primera amplitud. Por lo tanto, cualquier gráfico de Moore tiene el mínimo número de vértices posible entre todos los gráficos con grado mínimo d y circunferencia 2 k + 1 : es una jaula .

Para una circunferencia uniforme de 2 k , se puede formar de manera similar un árbol de búsqueda en anchura comenzando desde el 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

${\displaystyle 2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.}$

(En cambio, el lado derecho de la fórmula cuenta el número de vértices en un árbol de búsqueda de primer ancho a partir de un solo 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, a veces se define que las gráficas de Moore incluyen las gráficas que cumplen exactamente este límite. Una vez más, cualquier gráfico de este tipo debe ser una jaula.

Ejemplos

El teorema de Hoffman-Singleton establece que cualquier gráfico de Moore con circunferencia 5 debe tener grado 2, 3, 7 o 57. Los gráficos de Moore son: ^[3]

• Las gráficas completas K _n en n > 2 nodos (diámetro 1, circunferencia 3, grado n − 1 , orden n )
• Los ciclos impares C _{2 n +1} (diámetro n , circunferencia 2 n + 1 , grado 2, orden 2 n + 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)
• Un gráfico hipotético (o más de uno) 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 por vértices , el desconocido (si existe) no puede ser transitivo por vértices, ya que su grupo de automorfismos puede tener un orden como máximo de 375, menos que su número de vértices. ^[5]

Si se utiliza la definición generalizada de gráficas de Moore que permite gráficas de circunferencias pares, las gráficas de Moore de circunferencias pares corresponden a gráficas de incidencia de polígonos generalizados (posiblemente degenerados) . Algunos ejemplos son los ciclos pares C _{2 n} , los gráficos bipartitos completos K _{n , n} 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, es Se sabe que, además de las gráficas enumeradas anteriormente, todas las gráficas de Moore deben tener circunferencias 5, 6, 8 o 12. ^[6] El caso de circunferencia par también se deriva del teorema de Feit-Higman sobre posibles valores de n para una n generalizada - gon.

Ver también

• Tabla de los gráficos más grandes conocidos de un diámetro determinado y grado máximo

Notas

1. Azarija y Klavžar (2015).
2. Erdős, Rényi y Sós (1966).
3. Bollobás (1998), Teorema 19, p. 276.
4. Dalfó (2019).
5. Mačaj y Širáň (2010).
6. Bannai e Ito (1973); Damerell (1973)

Referencias

• Azarija, Jernej; Klavžar, Sandi (2015), "Los gráficos y ciclos de Moore son gráficos extremos para ciclos convexos", Journal of Graph Theory , 80 : 34–42, arXiv : 1210.6342 , doi : 10.1002/jgt.21837, S2CID  333785
• Bannai, E.; Ito, T. (1973), "On finite Moore Graphs", Revista de la Facultad de Ciencias de la Universidad de Tokio. Secta. 1 A, Matemáticas , 20 : 191–208, MR  0323615, archivado desde el original el 24 de abril de 2012
• Bollobás, Béla (1998), Teoría de grafos moderna , Textos de Posgrado en Matemáticas , vol. 184, Springer-Verlag.
• Dalfó, C. (2019), "Un estudio sobre el gráfico de Moore que falta" (PDF) , Álgebra lineal y sus aplicaciones , 569 : 1–14, doi :10.1016/j.laa.2018.12.035, hdl : 2117/127212 , SEÑOR  3901732, S2CID  126689579
• Damerell, RM (1973), "Sobre los gráficos de Moore", Procedimientos matemáticos de la Sociedad Filosófica de Cambridge , 74 (2): 227–236, Bibcode :1973PCPS...74..227D, doi :10.1017/S0305004100048015, MR  0318004
• Erdős, Paul ; Rényi, Alfred ; Sós, Vera T. (1966), "Sobre un problema de teoría de grafos" (PDF) , Studia Sci. Matemáticas. Hungría. , 1 : 215–235, archivado desde el original (PDF) el 9 de marzo de 2016 , consultado el 23 de febrero de 2010.
• 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
• Macaj, Martín; Širáň, Jozef (2010), "Búsqueda de propiedades del gráfico de Moore que falta", Álgebra lineal y sus aplicaciones , 432 (9): 2381–2398, doi : 10.1016/j.laa.2009.07.018.
• Singleton, Robert R. (1968), "No existe 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.
• Weisstein, Eric W. , "Moore Graph" ("Teorema de Hoffman-Singleton") en MathWorld .