En el campo matemático de la teoría de grafos , el gráfico de Coxeter es un gráfico de 3 regulares con 28 vértices y 42 aristas. [1] Es uno de los 13 gráficos cúbicos de distancia regular conocidos . [2] Lleva el nombre de Harold Scott MacDonald Coxeter .
El gráfico de Coxeter tiene número cromático 3, índice cromático 3, radio 4, diámetro 4 y circunferencia 7. También es un gráfico conectado con 3 vértices y un gráfico conectado con 3 aristas . Tiene un grosor de libro 3 y una cola número 2. [3]
El gráfico de Coxeter es hipohamiltoniano : no tiene en sí mismo un ciclo hamiltoniano, pero cada gráfico formado eliminando un solo vértice es hamiltoniano. Tiene el número de cruce rectilíneo 11 y es el gráfico cúbico más pequeño con ese número de cruce [4] (secuencia A110507 en la OEIS ).
La construcción más sencilla de un gráfico de Coxeter es a partir de un plano de Fano . Tome las 7 C 3 = 35 3 combinaciones posibles en 7 objetos. Descarta los 7 trillizos que corresponden a las líneas del plano de Fano, quedando 28 trillizos. Enlaza dos trillizos si están separados. El resultado es el gráfico de Coxeter. (Ver imagen.) Esta construcción exhibe el gráfico de Coxeter como un subgrafo inducido del gráfico impar O 4 , también conocido como gráfico de Kneser KG 7,3 .
El gráfico de Coxeter también se puede construir a partir del gráfico de Heawood de distancia regular más pequeña construyendo un vértice para cada 6 ciclos en el gráfico de Heawood y un borde para cada par disjunto de 6 ciclos. [5]
El gráfico de Coxeter puede derivarse del gráfico de Hoffman-Singleton . Tome cualquier vértice v en el gráfico de Hoffman-Singleton. Existe un conjunto independiente de talla 15 que incluye v . Elimina los 7 vecinos de v y todo el conjunto independiente incluido v , dejando atrás el gráfico de Coxeter.
El grupo de automorfismos del gráfico de Coxeter es un grupo de orden 336. [6] Actúa transitivamente sobre los vértices, las aristas y los arcos del gráfico. Por tanto, la gráfica de Coxeter es una gráfica simétrica . 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 gráfico de Coxeter, denominado F28A, es el único gráfico simétrico cúbico con 28 vértices. [7]
El gráfico de Coxeter también está determinado únicamente por su espectro de gráfico , el conjunto de valores propios del gráfico de su matriz de adyacencia . [8]
Como gráfico transitivo de vértice finito conectado que no contiene 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 es verificada por el gráfico de Coxeter.
Sólo se conocen cinco ejemplos de gráfico transitivo de vértices sin ciclos hamiltonianos: el gráfico completo K 2 , el gráfico de Petersen , el gráfico de Coxeter y dos gráficos derivados de los gráficos de Petersen y Coxeter reemplazando cada vértice con un triángulo. [9]
El polinomio característico del gráfico de Coxeter es . Es el único gráfico con este polinomio característico, por lo que es un gráfico determinado por su espectro.
Estas son 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).
