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 gráficos regulares de distancia cúbica conocidos . [2] Lleva el nombre de Harold Scott MacDonald Coxeter .
Gráfico de Coxeter | |
---|---|
![]() El gráfico de Coxeter | |
Lleva el nombre de | HSM Coxeter |
Vértices | 28 |
Bordes | 42 |
Radio | 4 |
Diámetro | 4 |
Circunferencia | 7 |
Automorfismos | 336 ( PGL 2 (7)) |
Número cromático | 3 |
Índice cromático | 3 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Simétrica Distancia-regular Distancia-transitiva Cúbica Hipohamiltoniana |
Tabla de gráficos y parámetros |
Propiedades
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 de 3 vértices conectados y un gráfico de 3 bordes conectados . Tiene un grosor de libro 3 y un número de cola 2. [3]
El gráfico de Coxeter es hipohamiltoniano : no tiene en sí mismo un ciclo hamiltoniano, pero cada gráfico formado al eliminar 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 ).
Construcción
La construcción más simple de un gráfico de Coxeter es de un plano de Fano . Tome las 7 C 3 = 35 posibles 3 combinaciones en 7 objetos. Descarta los 7 tripletes que corresponden a las líneas del plano de Fano, quedando 28 tripletes. Vincula dos trillizos si están separados. El resultado es el gráfico de Coxeter. Esta construcción muestra el gráfico de Coxeter como un subgráfico inducido del gráfico 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ño mediante la construcción de 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 se puede derivar del gráfico de Hoffman-Singleton . Tome cualquier vértice v en la gráfica de Hoffman-Singleton. Hay un conjunto independiente de tamaño 15 que incluye v . Elimine los 7 vecinos de v , y todo el conjunto independiente, incluido v , dejando atrás el gráfico de Coxeter.
Propiedades algebraicas
El grupo de automorfismos del grafo de Coxeter es un grupo de orden 336. [6] Actúa de forma transitiva sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, la gráfica de Coxeter es simétrica . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier borde a cualquier otro borde. Según el censo de Foster , el gráfico de Coxeter, al que se hace referencia como F28A, es el único gráfico simétrico cúbico en 28 vértices. [7]
El gráfico de Coxeter también está determinado de forma única por su espectro de gráfico , el conjunto de valores propios de gráfico de su matriz de adyacencia . [8]
Como un gráfico transitivo de vértice conectado finito que no contiene un 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.
Solo se conocen cinco ejemplos de gráfico transitivo de vértice 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, lo que lo convierte en un gráfico determinado por su espectro.
Galería
El gráfico obtenido por cualquier escisión de borde del Coxeter está conectado con Hamilton.
El número cromático del gráfico de Coxeter es 3.
El número de cruce rectilíneo del gráfico de Coxeter es 11.
Referencias
- ^ Weisstein, Eric W. "Gráfico de Coxeter" . MathWorld .
- ^ Brouwer, AE; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
- ^ Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ Haythorpe, Michael; Newcombe, Alex (2018), No hay gráficos cúbicos en 26 vértices con el número de cruce 11 , arXiv : 1804.10336
- ^ Dejter, Italo J. (2011), "Del gráfico de Coxeter al gráfico de Klein", Journal of Graph Theory , arXiv : 1002.1960 , doi : 10.1002 / jgt.20597.
- ↑ Royle, G. F028A data [ enlace muerto permanente ]
- ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes hasta 768 vértices". J. Combin. Matemáticas. Combin. Computación. 40, 41-63, 2002.
- ^ ER van Dam y WH Haemers, caracterizaciones espectrales de algunos gráficos de distancia regular. J. Algebraic Combin. 15, páginas 189-202, 2003
- ^ Royle, G. "Gráficos simétricos cúbicos (el censo de Foster)".
- Coxeter, HSM "Mi gráfico". Proc. London Math. Soc. 46, 117-136, 1983.