Gráfico de Coxeter

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 distancia-regulares conocidos . ^{[ 2 ]} Recibe su 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 3-conexo por vértices y un grafo 3-conexo por aristas . Tiene grosor de libro 3 y número de cola 2. ^{[ 3 ]}

El grafo de Coxeter es hipohamiltoniano : no posee un ciclo hamiltoniano, pero todo grafo formado al eliminar un solo vértice es hamiltoniano. Tiene un número de cruces rectilíneos de 11 y es el grafo cúbico más pequeño con ese número de cruces ^{[ 4 ]} (secuencia A110507 en la OEIS ) . El grafo es 1-planar . ^{[ 5 ]}

La construcción más simple de un grafo de Coxeter se obtiene a partir de un plano de Fano . Se toman las ⁷ C ₃ = 35 posibles combinaciones de 3 elementos en 7 objetos. Se descartan las 7 ternas que corresponden a las líneas del plano de Fano, quedando 28 ternas. Se unen dos ternas si son disjuntas. 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 ₄ , también conocido como el grafo de Kneser KG _7,3 .

El grafo de Coxeter también puede construirse a partir del grafo de Heawood, más pequeño y regular en distancia , construyendo un vértice por cada ciclo de 6 miembros en el grafo de Heawood y una arista por cada par disjunto de ciclos de 6 miembros. ^{[ 6 ]}

El grafo de Coxeter se puede derivar del grafo de Hoffman-Singleton . Tomemos cualquier vértice v en el grafo de Hoffman-Singleton. Existe un conjunto independiente de tamaño 15 que incluye a v . Eliminemos los 7 vecinos de v y todo el conjunto independiente que incluye a v , obteniendo así el grafo de Coxeter.

El grupo de automorfismos del grafo de Coxeter es un grupo de orden 336. ^{[ 7 ]} Actúa transitivamente sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el grafo de Coxeter es un grafo simétrico . Posee automorfismos que transforman cualquier vértice en cualquier otro vértice y cualquier arista en cualquier otra arista. Según el censo de Foster , el grafo de Coxeter, denominado F28A, es el único grafo cúbico simétrico de 28 vértices. ^{[ 8 ]}

El grafo de Coxeter también está determinado de forma única por su espectro de grafos , el conjunto de valores propios del grafo de su matriz de adyacencia . ^{[ 9 ]}

Como grafo finito, conexo y transitivo por vértices que no contiene ningún ciclo hamiltoniano , el grafo de Coxeter es un contraejemplo a una variante de la conjetura de Lovász , pero la formulación canónica de la conjetura exige un camino hamiltoniano y es verificada por el grafo de Coxeter.

Solo se conocen cinco ejemplos de grafos transitivos en vértices sin ciclos hamiltonianos  : el grafo completo K ₂ , el grafo de Petersen , el grafo de Coxeter y dos grafos derivados de los grafos de Petersen y Coxeter reemplazando cada vértice por un triángulo. ^{[ 10 ]}

El polinomio característico del gráfico de Coxeter es${\displaystyle (x-3)(x-2)^{8}(x+1)^{7}(x^{2}+2x-1)^{6}}$Es la única gráfica con este polinomio característico, lo que la convierte en una gráfica determinada por su espectro.

• Coxeter, HSM "Mi grafo." Proc. London Math. Soc. 46, 117-136, 1983.