En la teoría de grafos , el teorema de Grinberg es una condición necesaria para que un grafo plano contenga un ciclo hamiltoniano , basado en las longitudes de sus ciclos faciales. El resultado se ha utilizado ampliamente para construir gráficos planos no hamiltonianos con propiedades adicionales, como para dar nuevos contraejemplos a la conjetura de Tait (originalmente refutada por WT Tutte en 1946). Este teorema fue probado por el matemático letón Emanuel Grinberg en 1968.
Formulación
Sea G un gráfico plano finito con un ciclo hamiltoniano C , con una incrustación plana fija. Denote por ƒ k y g k el número de k -caras gonales de la incrustación que están dentro y fuera de C , respectivamente. Luego
La demostración es una consecuencia fácil de la fórmula de Euler .
Como corolario de este teorema, si un gráfico plano incrustado tiene solo una cara cuyo número de lados no es 2 mod 3, y las caras restantes tienen todos números de lados que son 2 mod 3, entonces el gráfico no es hamiltoniano. En este caso, solo la primera cara contribuye al valor mod-3 de la suma y hace que la suma sea distinta de cero. El factor de k - 2 en las contribuciones de las otras caras hace que sus contribuciones sean cero mod 3. Por ejemplo, para el gráfico de la figura, todas las caras limitadas tienen 5 u 8 lados, pero la cara ilimitada tiene 9 lados, por lo que satisface esta condición y no es hamiltoniano.
Aplicaciones
Grinberg usó su teorema para encontrar gráficos poliédricos cúbicos no hamiltonianos con alta conectividad de borde cíclico. La conectividad de aristas cíclicas de un gráfico es el número más pequeño de aristas cuya eliminación deja un subgrafo con más de un componente cíclico. El gráfico de Tutte de 46 vértices , y los gráficos poliédricos cúbicos no hamiltonianos más pequeños derivados de él, tienen tres aristas cíclicas de conectividad. Grinberg usó su teorema para encontrar un gráfico poliédrico cúbico no hamiltoniano con 44 vértices, 24 caras y conectividad de borde cíclico cuatro, y otro ejemplo (que se muestra en la figura) con 46 vértices, 25 caras y conectividad de borde cíclico cinco, el máximo posible conectividad de borde cíclico para un gráfico plano cúbico distinto de K 4 . En el ejemplo que se muestra, todas las caras delimitadas tienen cinco u ocho aristas, las cuales son números que son 2 mod 3, pero la cara ilimitada tiene nueve aristas, diferentes a 2 mod 3. Por lo tanto, según el corolario del teorema de Grinberg , el gráfico no puede ser hamiltoniano.
El teorema de Grinberg también se ha utilizado para encontrar gráficas hipohamiltonianas planas , gráficas que no son hamiltonianas pero que pueden hacerse hamiltonianas eliminando cualquier vértice. De nuevo, la construcción hace que todas las caras menos una tengan varios bordes congruentes con 2 mod 3 ( Thomassen 1976 , Wiener & Araya 2009 ). Thomassen (1981) usa el teorema de una manera algo más complicada para encontrar un gráfico hipohamiltoniano cúbico plano: el gráfico que construye incluye una cara de 4 aristas adyacente a cuatro caras de 7 aristas, y todas las demás caras tienen cinco u ocho aristas. Para satisfacer el teorema de Grinberg, un ciclo hamiltoniano tendría que separar una de las caras de 4 o 7 aristas de las otras cuatro, lo que no es posible.
Limitaciones
Existen gráficos planos no hamiltonianos en los que todas las caras tienen cinco u ocho lados. Para estos gráficos, la fórmula de Grinberg tomada en módulo tres siempre se satisface mediante cualquier partición de las caras en dos subconjuntos, lo que impide la aplicación de su teorema para demostrar la no hamiltonicidad en este caso ( Zaks 1977 ).
No es posible usar el teorema de Grinberg para encontrar contraejemplos de la conjetura de Barnette , que todo grafo poliédrico bipartito cúbico es hamiltoniano. Cada grafo poliédrico bipartito cúbico tiene una partición de las caras en dos subconjuntos que satisfacen el teorema de Grinberg, independientemente de si también tiene un ciclo hamiltoniano ( Krooss 2004 ).
Referencias
- Grinberg, È. Ja. (1968), "Gráficos planos homogéneos de grado tres sin circuitos hamiltonianos", Letonia Math. Anuario 4 (en ruso), Riga: Izdat. “Zinatne”, págs. 51–58, MR 0238732. Traducción al inglés de Dainis Zeps, arXiv : 0908.2563 .
- Krooss, André (2004), "Die Barnette'sche Vermutung und die Grinberg'sche Formel", Analele Universităţii din Craiova. Seria Matematică-Informatică (en alemán), 31 : 59–65, MR 2153849.
- Malkevitch, Joseph (enero de 2005), Fórmula poliédrica de Euler: Parte II , columna de características, American Mathematical Society.
- Thomassen, Carsten (1976), "Grafos planos e infinitos hipohamiltonianos e hipotraceables", Matemáticas discretas , 14 (4): 377–389, doi : 10.1016 / 0012-365X (76) 90071-6 , MR 0422086.
- Thomassen, Carsten (1981), " Gráficas planas cúbicas hipo-hamiltonianas e hipotraceables", Journal of Combinatorial Theory , Serie B, 30 (1): 36–44, doi : 10.1016 / 0095-8956 (81) 90089-7 , MR 0609592.
- Wiener, Gábor; Araya, Makoto (2009), The ultimate question , arXiv : 0904.3012 , Bibcode : 2009arXiv0904.3012W.
- Tutte, WT (1998), "Capítulo 2: Caballeros andantes", Teoría de grafos como la he conocido , Oxford Lecture Series in Mathematics and its Applications, 11 , Nueva York: The Clarendon Press Oxford University Press, ISBN 0-19-850251-6, MR 1635397.
- Zaks, Joseph (1977), "Gráficos no hamiltonianos no grinbergianos", Matemáticas discretas , 17 (3): 317–321, doi : 10.1016 / 0012-365X (77) 90165-0 , MR 0460189.
enlaces externos
- Gráficos de Grinberg , de MathWorld .