Gráfica de Wagner

Gráfica de Wagner
Gráfica de Wagner
	El gráfico de Wagner
Llamado en honor a	Klaus Wagner
Vértices	8
Bordes	12
Radio	2
Diámetro	2
Circunferencia	4
Automorfismos	16 ( D 8 )
Número cromático	3
Índice cromático	3
Género	1
Espectro	( 3 1 2 − 1 − 1 − 2 − 1 1 2 2 1 2 ) {\displaystyle {\begin{pmatrix}3&1&{\sqrt {2}}-1&-1&-{\sqrt {2}}-1\\1&2&2&1&2\end{pmatrix}}}
Propiedades	Ápice toroidal transitivo de vértice libre de triángulos ; hamiltonianos cúbicos; ; ; ;
Notación	M 8
	Tabla de gráficos y parámetros

Grafo cúbico con 8 vértices y 12 aristas

En el campo matemático de la teoría de grafos , el grafo de Wagner es un grafo regular de 3 con 8 vértices y 12 aristas. ^[1] Es el grafo de escalera de Möbius de 8 vértices .

Propiedades

Como escalera de Möbius, el grafo de Wagner no es plano , pero tiene un número de cruce uno, lo que lo convierte en un grafo de vértice . Puede estar incrustado sin cruces en un toro o plano proyectivo , por lo que también es un grafo toroidal . Tiene circunferencia 4, diámetro 2, radio 2, número cromático 3, índice cromático 3 y está conectado por 3 vértices y por 3 aristas .

El grafo de Wagner tiene 392 árboles de expansión ; éste y el grafo bipartito completo $K 3,3$ tienen la mayor cantidad de árboles de expansión entre todos los grafos cúbicos con el mismo número de vértices. ^[2]

El grafo de Wagner es un grafo transitivo por vértices pero no por aristas . Su grupo de automorfismos completo es isomorfo al grupo diedro $D 8$ de orden 16, el grupo de simetrías de un octógono , que incluye tanto rotaciones como reflexiones.

El polinomio característico del gráfico de Wagner es

(x-3)(x-1)^{2}(x+1)(x^{2}+2x-1)^{2}.

Es el único grafo con este polinomio característico, por lo que es un grafo determinado por su espectro .

El grafo de Wagner no tiene triángulos y tiene independencia número tres, lo que proporciona la mitad de la prueba de que el número de Ramsey $R (3,4)$ (el menor número $n$ tal que cualquier grafo $de n$ vértices contiene un triángulo o un conjunto independiente de cuatro vértices) es 9. ^[3]

Gráficos menores

Las escaleras de Möbius desempeñan un papel importante en la teoría de grafos menores . El primer resultado de este tipo es un teorema de Klaus Wagner de 1937 (parte de un conjunto de resultados conocido como teorema de Wagner ) que establece que los grafos sin menor K ₅ pueden formarse utilizando operaciones de suma de clique para combinar grafos planares y la escalera de Möbius M ₈ . ^[4] Por esta razón, M ₈ se denomina grafo de Wagner.

El grafo de Wagner es también uno de los cuatro menores prohibidos mínimos para los grafos de ancho de árbol como máximo tres (los otros tres son el grafo completo K ₅ , el grafo del octaedro regular y el grafo del prisma pentagonal ) y uno de los cuatro menores prohibidos mínimos para los grafos de ancho de rama como máximo tres (los otros tres son K ₅ , el grafo del octaedro y el grafo cúbico ). ^[5]^[6]

Construcción

El grafo de Wagner es un grafo hamiltoniano cúbico y se puede definir mediante la notación LCF [4] ⁸ . Es una instancia de un grafo de Andrásfai , un tipo de grafo circulante en el que los vértices se pueden organizar en un ciclo y cada vértice está conectado a los otros vértices cuyas posiciones difieren en un número que es 1 (mod 3). También es isomorfo a la clique circular $K$ $8/3$ .

Se puede dibujar como un gráfico de escalera con 4 peldaños hechos cíclicos en una banda de Möbius topológica .

Galería

El número cromático del grafo de Wagner es 3.
El índice cromático del gráfico de Wagner es 3.
El gráfico de Wagner dibujado en la cinta de Möbius.

Referencias

^ Bondy, JA ; Murty, USR (2007). Teoría de grafos . Springer. págs. 275-276. ISBN. 978-1-84628-969-9.
^ Jakobson, Dmitry; Rivin, Igor (1999). "Sobre algunos problemas extremos en teoría de grafos". arXiv : math.CO/9907050 .
^ Soifer, Alexander (2008). El libro de colorear matemático . Springer-Verlag. pág. 245. ISBN 978-0-387-74640-1.
^ Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen (en alemán). 114 (1): 570–590. doi :10.1007/BF01594196. S2CID 123534907.
^ Bodlaender, Hans L. (1998). "Un k -arboreto parcial de grafos con ancho de árbol acotado". Ciencias de la Computación Teórica . 209 (1–2): 1–45. doi :10.1016/S0304-3975(97)00228-4. hdl : 1874/18312 .
^ Bodlaender, Hans L. ; Thilikos, Dimitrios M. (1999). "Gráficos con ancho de rama de tres como máximo". Journal of Algorithms . 32 (2): 167–194. doi :10.1006/jagm.1999.1011. hdl : 1874/2734 .

[1] Bondy, JA ; Murty, USR (2007). Teoría de grafos . Springer. págs. 275-276. ISBN. 978-1-84628-969-9.

[2] Jakobson, Dmitry; Rivin, Igor (1999). "Sobre algunos problemas extremos en teoría de grafos". arXiv : math.CO/9907050 .

[3] Soifer, Alexander (2008). El libro de colorear matemático . Springer-Verlag. pág. 245. ISBN 978-0-387-74640-1.

[4] Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen (en alemán). 114 (1): 570–590. doi :10.1007/BF01594196. S2CID 123534907.

[5] Bodlaender, Hans L. (1998). "Un k -arboreto parcial de grafos con ancho de árbol acotado". Ciencias de la Computación Teórica . 209 (1–2): 1–45. doi :10.1016/S0304-3975(97)00228-4. hdl : 1874/18312 .

[6] Bodlaender, Hans L. ; Thilikos, Dimitrios M. (1999). "Gráficos con ancho de rama de tres como máximo". Journal of Algorithms . 32 (2): 167–194. doi :10.1006/jagm.1999.1011. hdl : 1874/2734 .