En el campo matemático de la teoría de grafos , el grafo de Gray es un grafo bipartito no dirigido con 54 vértices y 81 aristas . Es un gráfico cúbico : cada vértice toca exactamente tres aristas. Fue descubierto por Marion C. Gray en 1932 (inédito), luego descubierto de forma independiente por Bouwer 1968 en respuesta a una pregunta planteada por Jon Folkman 1967. El gráfico de Gray es interesante como el primer ejemplo conocido de un gráfico cúbico que tiene la propiedad algebraica de siendo borde pero no vértice transitivo (ver más abajo).
El gráfico de Gray tiene número cromático 2, índice cromático 3, radio 6 y diámetro 6. También es un gráfico no plano conectado con 3 vértices y 3 bordes .
El gráfico de Gray se puede construir (Bouwer 1972) a partir de los 27 puntos de una cuadrícula de 3 × 3 × 3 y las 27 líneas paralelas a los ejes que pasan por estos puntos. Esta colección de puntos y líneas forma una configuración proyectiva : cada punto tiene exactamente tres líneas que lo atraviesan, y cada línea tiene exactamente tres puntos. El gráfico de Gray es el gráfico de Levi de esta configuración; tiene un vértice para cada punto y cada línea de la configuración, y una arista para cada par de puntos y líneas que se tocan. Esta construcción se generaliza (Bouwer 1972) a cualquier dimensión n ≥ 3, produciendo un gráfico de Levi n -valente con propiedades algebraicas similares a las del gráfico de Gray. En (Monson, Pisanski, Schulte, Ivic-Weiss 2007), el gráfico de Gray aparece como un tipo diferente de gráfico de Levi para los bordes y las caras triangulares de un determinado 4-politopo regular abstracto localmente toroidal. Por tanto, es el primero de una familia infinita de gráficos cúbicos construidos de manera similar. Como ocurre con otros gráficos de Levi, es un gráfico bipartito , con los vértices correspondientes a puntos en un lado de la bipartición y los vértices correspondientes a líneas en el otro lado.
Marušič y Pisanski (2000) ofrecen varios métodos alternativos para construir el gráfico de Gray. Como ocurre con cualquier gráfico bipartito, no hay ciclos de longitud impar y tampoco hay ciclos de cuatro o seis vértices, por lo que la circunferencia del gráfico Gray es 8. La superficie orientada más simple en la que se puede incrustar el gráfico Gray tiene género 7 (Marušič, Pisanski y Wilson 2005).
El gráfico de Gray es hamiltoniano y se puede construir a partir de la notación LCF :
Como gráfico cúbico hamiltoniano, tiene índice cromático tres.
El grupo de automorfismo del gráfico de Gray es un grupo de orden 1296. Actúa transitivamente sobre las aristas del gráfico pero no sobre sus vértices: hay simetrías que llevan cada arista a cualquier otra arista, pero no llevan cada vértice a ningún otro vértice. Los vértices que corresponden a puntos de la configuración subyacente solo pueden ser simétricos con respecto a otros vértices que corresponden a puntos, y los vértices que corresponden a líneas solo pueden ser simétricos con respecto a otros vértices que corresponden a líneas. Por tanto, el gráfico de Gray es un gráfico semisimétrico , el gráfico semisimétrico cúbico más pequeño posible.
El polinomio característico del gráfico de Gray es
El gráfico de Gray se puede representar mediante puntos en el plano de tal manera que los vértices adyacentes estén separados por una unidad de distancia; es decir, es una gráfica de distancia unitaria . [1]
![{\displaystyle [-25,7,-7,13,-13,25]^{9}.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/014e670206b76bab2513b807e955533d50c3efb0)
