Hispanopedia WikiEn el campo matemático de la teoría de grafos , el grafo de Wagner es un grafo 3-regular con 8 vértices y 12 aristas. [ 1 ] Es el grafo escalera de Möbius de 8 vértices.
Propiedades
Como escalera de Möbius, el grafo de Wagner no es planar pero tiene un cruce número uno, lo que lo convierte en un grafo de vértice . Puede incrustarse 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 es 3 -conexo por vértices y 3 -conexo por aristas .
El grafo de Wagner tiene 392 árboles de expansión ; este 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 en vértices, pero no transitivo en aristas . Su grupo de automorfismos completo es isomorfo al grupo diedral 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
Es la única gráfica con este polinomio característico, lo que la convierte en una gráfica determinada por su espectro .
El grafo de Wagner no contiene triángulos y tiene un número de independencia 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 ]
menores de grafos
Las escaleras de Möbius desempeñan un papel importante en la teoría de los menores de grafos . El primer resultado de este tipo es un teorema de 1937 de Klaus Wagner (parte de un conjunto de resultados conocido como el teorema de Wagner ) que establece que se pueden formar grafos sin un menor K 5 utilizando operaciones de suma de cliques para combinar grafos planares y la escalera de Möbius M 8 . [ 4 ] Por esta razón, M 8 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 5 , 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 5 , el grafo del octaedro y el grafo del cubo ). [ 5 ] [ 6 ]
Construcción
El grafo de Wagner es un grafo hamiltoniano cúbico y se puede definir mediante la notación LCF [4] 8 . 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 demás 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 representar como un gráfico de escalera con 4 peldaños dispuestos cíclicamente sobre una cinta de Möbius topológica .
Galería
El número cromático del gráfico de Wagner es 3.
El índice cromático del gráfico de Wagner es 3.
El gráfico de Wagner dibujado sobre 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 extremales en teoría de grafos". arXiv : math.CO/9907050 .
- ↑ Soifer, Alexander (2008). El libro para 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". Theoretical Computer Science . 209 ( 1–2 ): 1–45 . doi : 10.1016/S0304-3975(97)00228-4 . hdl : 1874/18312 .
- ↑ Bodlaender, Hans L. ; Thilikos, Dimitrios M. (1999). "Grafos con ancho de rama como máximo tres". Journal of Algorithms . 32 (2): 167– 194. doi : 10.1006/jagm.1999.1011 . hdl : 1874/2734 .
- Gráficos individuales
- Gráficos regulares