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 .
Como escalera de Möbius, el grafo de Wagner no es plano , pero tiene un cruce número 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
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]
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 5 pueden formarse utilizando operaciones de suma de clique 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 cúbico ). [5] [6]
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 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 .
