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 grafo cúbico : cada vértice toca exactamente tres aristas. Fue descubierto por Marion C. Gray en 1932 (inédito), y luego descubierto independientemente por Bouwer en 1968 en respuesta a una pregunta planteada por Jon Folkman en 1967. El grafo de Gray es interesante como el primer ejemplo conocido de un grafo cúbico que tiene la propiedad algebraica de ser transitivo en aristas pero no en vértices (ver más abajo).
El grafo de Gray tiene número cromático 2, índice cromático 3, radio 6 y diámetro 6. También es un grafo no plano conexo por 3 vértices y conexo por 3 aristas .
El grafo de Gray puede construirse (Bouwer 1972) a partir de los 27 puntos de una cuadrícula de 3 × 3 × 3 y las 27 líneas paralelas al eje 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 en ella. El grafo de Gray es el grafo 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 un punto y una línea que se tocan entre sí. Esta construcción se generaliza (Bouwer 1972) a cualquier dimensión n ≥ 3, produciendo un grafo de Levi n -valente con propiedades algebraicas similares a las del grafo de Gray. En (Monson, Pisanski, Schulte, Ivic-Weiss 2007), el grafo de Gray aparece como un tipo diferente de grafo de Levi para las aristas y las caras triangulares de un cierto 4-politopo regular abstracto localmente toroidal. Por lo tanto, es el primero de una familia infinita de grafos cúbicos construidos de manera similar. Al igual que otros grafos de Levi, es un grafo 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 grafo de Gray. Como en cualquier grafo bipartito, no hay ciclos de longitud impar ni tampoco ciclos de cuatro o seis vértices, por lo que la circunferencia del grafo de Gray es 8. La superficie orientada más simple en la que se puede incrustar el grafo de 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 MCF :
Como gráfico cúbico hamiltoniano, tiene índice cromático tres.
El grupo de automorfismos del grafo de Gray es un grupo de orden 1296. Actúa transitivamente sobre las aristas del grafo pero no sobre sus vértices: hay simetrías que llevan cada arista a cualquier otra arista, pero no que llevan cada vértice a cualquier otro vértice. Los vértices que corresponden a puntos de la configuración subyacente sólo pueden ser simétricos a otros vértices que correspondan a puntos, y los vértices que corresponden a rectas sólo pueden ser simétricos a otros vértices que correspondan a rectas. Por tanto, el grafo de Gray es un grafo semisimétrico , el grafo 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 distancia unitaria; es decir, es un gráfico de distancia unitaria . [1]
![{\displaystyle [-25,7,-7,13,-13,25]^{9}.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/014e670206b76bab2513b807e955533d50c3efb0)
