En el campo matemático de la teoría de grafos , el grafo de Coxeter es un grafo 3-regular con 28 vértices y 42 aristas. [1] Es uno de los 13 grafos cúbicos regulares de distancia conocidos . [2] Lleva el nombre de Harold Scott MacDonald Coxeter .
El grafo de Coxeter tiene número cromático 3, índice cromático 3, radio 4, diámetro 4 y circunferencia 7. También es un grafo conexo por 3 vértices y un grafo conexo por 3 aristas . Tiene un grosor de libro de 3 y un número de cola de 2. [3]
El grafo de Coxeter es hipohamiltoniano : no tiene en sí un ciclo hamiltoniano, pero todo grafo formado al eliminar un único vértice de él es hamiltoniano. Tiene un número de cruce rectilíneo 11 y es el grafo cúbico más pequeño con ese número de cruce [4] (secuencia A110507 en la OEIS ).
La construcción más simple de un grafo de Coxeter es a partir de un plano de Fano . Tome las 7 C 3 = 35 posibles combinaciones de 3 en 7 objetos. Descarte los 7 tripletes que corresponden a las líneas del plano de Fano, dejando 28 tripletes. Vincule dos tripletes si son disjuntos. El resultado es el grafo de Coxeter. (Véase la imagen.) Esta construcción muestra el grafo de Coxeter como un subgrafo inducido del grafo impar O 4 , también conocido como el grafo de Kneser KG 7,3 .
El gráfico de Coxeter también se puede construir a partir del gráfico de Heawood regular de distancia más pequeña construyendo un vértice para cada ciclo de 6 en el gráfico de Heawood y un borde para cada par disjunto de ciclos de 6. [5]
El grafo de Coxeter puede derivarse del grafo de Hoffman-Singleton . Tome cualquier vértice v en el grafo de Hoffman-Singleton. Hay un conjunto independiente de tamaño 15 que incluye a v . Elimine los 7 vecinos de v y todo el conjunto independiente que incluye a v , dejando atrás el grafo de Coxeter.
El grupo de automorfismos del grafo de Coxeter es un grupo de orden 336. [6] Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por tanto, el grafo de Coxeter es un grafo simétrico . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Según el censo de Foster , el grafo de Coxeter, referenciado como F28A, es el único grafo cúbico simétrico sobre 28 vértices. [7]
El gráfico de Coxeter también está determinado de forma única por su espectro gráfico , el conjunto de valores propios del gráfico de su matriz de adyacencia . [8]
Como un gráfico transitivo de vértice conexo finito que no contiene ningún ciclo hamiltoniano , el gráfico de Coxeter es un contraejemplo de una variante de la conjetura de Lovász , pero la formulación canónica de la conjetura pide un camino hamiltoniano y se verifica mediante el gráfico de Coxeter.
Sólo se conocen cinco ejemplos de grafos transitivos de vértice sin ciclos hamiltonianos: el grafo completo K 2 , el grafo de Petersen , el grafo de Coxeter y dos grafos derivados de los grafos de Petersen y Coxeter reemplazando cada vértice con un triángulo. [9]
El polinomio característico del grafo de Coxeter es . Es el único grafo con este polinomio característico, lo que lo convierte en un grafo determinado por su espectro.
Se trata de representaciones diferentes del gráfico de Coxeter, que utilizan las mismas etiquetas de vértice. Hay cuatro colores y siete vértices de cada color.
Cada vértice rojo, verde o azul está conectado con dos vértices del mismo color (bordes delgados que forman 7 ciclos) y con un vértice blanco (bordes gruesos).
