Conde de gris

El gráfico de Gray  es un gráfico no dirigido bipartito con 54 vértices y 81 aristas. El gráfico es cúbico  : cualquier vértice pertenece exactamente a tres aristas. El gráfico fue descubierto por Gray en 1932 (sin publicación), luego descubierto de forma independiente por Bouwer en 1968 en respuesta a una pregunta planteada por Folkman en 1967. El gráfico de Gray es notable como históricamente el primer ejemplo de un gráfico cúbico que tiene la propiedad algebraica de transitividad de borde pero no de vértice.

El número cromático del gráfico Gray es 2, el índice cromático  es 3 y el radio y el diámetro son 6. También es un gráfico no plano conectado por 3 vértices y 3 bordes .

Edificio

El gráfico de Gray se puede construir [1] a partir de 27 puntos de una red de 3×3×3 y 27 líneas paralelas a los ejes y que pasan por estos puntos. Este conjunto de puntos y líneas forma una configuración proyectiva  : exactamente tres líneas pasan por cada punto y exactamente tres puntos se encuentran en cada línea. El gráfico de Gray es el gráfico de Levi de esta configuración. El gráfico tiene un vértice para cada punto y para cada recta de esta configuración, y una arista para cada par punto-recta si el punto está sobre la recta. Esta construcción se puede generalizar (Bauwer 1972) a cualquier dimensión , dando gráficos de Lévy de -valencia con propiedades algebraicas similares a las del gráfico de Gray.

También se puede construir como un gráfico de Levi para los bordes y las caras triangulares de algunos 4 politopos regulares abstractos localmente toroidales [2] .

Marusic y Pisanski [3] dieron algunos métodos alternativos para construir un gráfico de Gray. Como cualquier otro gráfico bipartito, el gráfico de Gray no contiene ciclos de longitud impar, ni ciclos con cuatro o seis vértices, por lo que la circunferencia de un gráfico de Gray es 8. La superficie orientada más simple en la que se puede incrustar un gráfico de Gray. es del género 7 [4] .

El gráfico de Gray es hamiltoniano y se puede construir a partir de la notación LCF :

Propiedades algebraicas

El grupo de automorfismos del grafo Gray es un grupo de orden 1296. Actúa transitivamente sobre las aristas del grafo, pero no sobre sus vértices - hay automorfismos que llevan cualquier arista a cualquier otra arista, pero no hay automorfismos que lleven ninguna vértice a cualquier otro. Los vértices correspondientes a la configuración subyacente al gráfico solo pueden ser simétricos a los vértices correspondientes a los puntos de configuración, y los vértices correspondientes a las líneas son simétricos solo a los vértices correspondientes a las líneas. Por lo tanto, el gráfico de Gray es un grupo semisimétrico y es el gráfico semisimétrico cúbico más pequeño posible.

El polinomio característico del gráfico de Gray es:

Galería

• conde de gris

• El número cromático del Conde Grey es 2.

• el índice cromático del gráfico de Gray es 3.

• La configuración subyacente de Graph Gray.

Notas

1. ↑ Bouwer, 1972 .
2. ↑ Monson, Pisanski, Schulte, Ivic-Weiss, 2007 .
3. ↑ Marusic, Pisanski, 2000 .
4. ↑ Marušič, Pisanski, Wilson, 2005 .

Enlaces

• Un gráfico cúbico transitivo de borde pero no de vértice // Boletín de la Sociedad Matemática Canadiense. - 1968. - T. 11 . — S. 533–535 . -doi : 10.4153 / CMB-1968-063-0 . .
• IZ Bouwer. Gráficos regulares transitivos en el borde pero no en el vértice // Journal of Combinatorial Theory, Serie B. - 1972. - Vol. 12 . — P. 32–40 . - doi : 10.1016/0095-8956(72)90030-5 . .
• J. Folkman. Gráficos simétricos de líneas regulares // Journal of Combinatorial Theory. - 1967. - T. 3 , nº. 3 . — S. 533–535 . - doi : 10.1016/S0021-9800(67)80069-3 . .
• Dragan Marušic, Tomaž Pisanski. El gráfico de Gray revisitado  // Journal of Graph Theory. - 2000. - T. 35 . — P. 1–7 . -doi : 10.1002 / 1097-0118(200009)35:1<1::AID-JGT1>3.0.CO;2-7 . .
• Dragan Marusic, Tomaž Pisanski, Steve Wilson. El género del gráfico Gray es 7 // European Journal of Combinatorics. - 2005. - T. 26 , núm. 3–4 . — S. 377–385 . -doi : 10.1016/ j.ejc.2004.01.015 . .
• B. Monson, T. Pisanski, E. Schulte, A. Ivic-Weiss. Gráficos semisimétricos de politopos // Journal of Combinatorial Theory, Serie A. - 2007. - Vol. 114 , no. 3 . — S. 421–435 . -doi : 10.1016/ j.jcta.2006.06.007 .
• Weisstein, Eric W. Gray Graph  (inglés) en el sitio web de Wolfram MathWorld .
• El gráfico gris es el gráfico más pequeño de su tipo . Archivado el 22 de febrero de 2014 en Wayback Machine , desde MathWorld .