En 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 gráfico de escalera de Möbius de 8 vértices .
Gráfico de Wagner | |
---|---|
![]() El gráfico de Wagner | |
Lleva el nombre de | 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 |
Propiedades | Ápice toroidal transitivo de vértice sin triángulo hamiltoniano cúbico |
Notación | M 8 |
Tabla de gráficos y parámetros |
Propiedades
Como escalera de Möbius, el gráfico de Wagner no es plano pero tiene el cruce número uno, lo que lo convierte en un gráfico de vértice . Se puede incrustar sin cruces en un plano toroidal o proyectivo , por lo que también es un gráfico 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 bordes .
El gráfico de Wagner tiene 392 árboles de expansión ; éste y el gráfico completo K 3,3 tienen la mayor cantidad de árboles de expansión entre todos los gráficos cúbicos con el mismo número de vértices. [2]
El gráfico de Wagner es un gráfico de vértice transitivo pero no de borde transitivo . 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. Es el único gráfico con este polinomio característico, lo que lo convierte en un gráfico determinado por su espectro.
El gráfico de Wagner no tiene 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 gráfico de n -vértices contiene un triángulo o un vértice de cuatro conjunto independiente) es 9. [3]
Graficar menores
Las escaleras de Möbius juegan un papel importante en la teoría de grafos menores . El resultado más antiguo de este tipo es un teorema de Klaus Wagner de 1937 (parte de un grupo de resultados conocido como teorema de Wagner ) según el cual las gráficas sin K 5 menor se pueden formar usando operaciones de suma de clique para combinar gráficas planas y la escalera de Möbius M 8 . [4] Por esta razón, M 8 se denomina gráfico de Wagner.
El gráfico de Wagner es también uno de los cuatro menores mínimos prohibidos para los gráficos de ancho de árbol como máximo tres (los otros tres son el gráfico completo K 5 , el gráfico del octaedro regular y el gráfico del prisma pentagonal ) y uno de los cuatro gráficos mínimos. menores prohibidos para los gráficos de ancho de rama como máximo tres (los otros tres son K 5 , el gráfico del octaedro y el gráfico del cubo ). [5] [6]
Construcción
El gráfico de Wagner es un gráfico hamiltoniano cúbico y se puede definir mediante la notación LCF [4] 8 . Es una instancia de un gráfico de Andrásfai , un tipo de gráfico 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 camarilla circular K 8/3 .
Se puede dibujar como un gráfico de escalera con 4 peldaños cíclicos en una tira 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 en la tira de Möbius.
Referencias
- ^ Bondy, JA ; Murty, USR (2007). Teoría de grafos . Saltador. págs. 275-276. ISBN 978-1-84628-969-9.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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. pag. 245. ISBN 978-0-387-74640-1..
- ^ Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen . 114 (1): 570–590. doi : 10.1007 / BF01594196 . S2CID 123534907 .
- ^ Bodlaender, Hans L. (1998). "Un k -arboretum parcial de gráficos con ancho de árbol acotado". Informática 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 como máximo tres". Revista de algoritmos . 32 (2): 167-194. doi : 10.1006 / jagm.1999.1011 . hdl : 1874/2734 ..