Conde de Coxeter
| Conde de Coxeter | |
|---|---|
| picos | 28 |
| costillas | 42 |
| Radio | cuatro |
| Diámetro | cuatro |
| Circunferencia | 7 |
| automorfismos | 336 ( PGL 2 (7)) |
| Número cromático | 3 |
| índice cromático | 3 |
| Propiedades |
cúbico
hipohamiltonianos |
| Archivos multimedia en Wikimedia Commons | |
El gráfico de Coxeter es un gráfico regular de 3 con 28 vértices y 42 aristas [1] Se conocen todos los gráficos regulares de distancia cúbica [2] , el gráfico de Coxeter es uno de los 13 gráficos de este tipo.
Propiedades
El número cromático del gráfico es 3, el índice cromático es 3, el radio es 4, el diámetro es 4 y la circunferencia es 7. El gráfico también está conectado por 3 vértices y 3 bordes .
El gráfico de Coxeter es hipo -hamiltoniano: no contiene ciclos hamiltonianos, pero la eliminación de cualquier vértice lo convierte en hamiltoniano . El número de cruces rectilíneos del gráfico de Coxeter es 11, y este es el gráfico cúbico más pequeño conocido con ese número de cruces, aunque pueden existir gráficos con 26 vértices y 11 cruces [3] .
El gráfico de Coxeter se puede construir a partir del gráfico de Heawood regular de distancia algo más pequeño creando un vértice para cada ciclo de 6 en el gráfico de Heawood y un borde para cada par desconectado de ciclos de 6 [4] .
Propiedades algebraicas
El grupo de automorfismos de un gráfico de Coxeter es un grupo de orden 336 [5] . Actúa transitivamente sobre los vértices y aristas del grafo, por lo que el grafo de Foster es simétrico . El gráfico tiene automorfismos que asignan cualquier vértice a cualquier otro y cualquier borde a cualquier otro borde. En la lista de Foster, el gráfico de Coxeter, listado como F28A, es el único gráfico simétrico cúbico con 28 vértices [6] .
El gráfico de Coxeter está determinado únicamente por su espectro , el conjunto de valores propios de la matriz de adyacencia del gráfico [7] .
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 Lavash , pero la formulación canónica de la conjetura requiere la presencia de un ciclo hamiltoniano.
Solo se conocen cinco gráficos transitivos de vértice sin ciclos hamiltonianos: el gráfico K 2 completo , el gráfico de Petersen , el gráfico de Coxeter y dos gráficos obtenidos a partir de los gráficos de Petersen y Coxeter reemplazando cada vértice con un triángulo [8] .
El polinomio característico del gráfico de Coxeter es . El gráfico es el único gráfico con tal polinomio, lo que hace que el gráfico esté definido únicamente por su espectro.
Galería
-
El gráfico obtenido al eliminar cualquier borde del gráfico de Coxeter es hamiltoniano conectado .
-
El número cromático del gráfico de Coxeter es 3.
-
El número de cruces rectilíneos del gráfico de Coxeter es 11.
Notas
- ↑ Weisstein, Eric W. Coxeter Gráfico en el sitio web Wolfram MathWorld .
- ↑ AE Brouwer, A. M. Cohen, A. Neumaier. Gráficos de distancia-regulares - Nueva York: Springer-Verlag, 1989.
- ↑ Secuencia OEIS A110507 _
- ↑ Italo J. Dejter. Del gráfico de Coxeter al gráfico de Klein // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002.1960 . .
- ↑ Royle, G. Datos de F028A (enlace descendente)
- ↑ M. Conder, P. Dobcsányi, "Gráficos simétricos trivalentes hasta 768 vértices". J. Combina. Matemáticas. Combinar. computar 40, 41-63, 2002.
- ↑ ER van Dam y WH Haemers, Caracterizaciones espectrales de algunos gráficos regulares de distancia. J. Combinación algebraica. 15, páginas 189-202, 2003
- ↑ Royle, G. "Gráficos simétricos cúbicos (El censo de Foster)". Archivado desde el original el 20 de julio de 2008.