Teorema de Greenberg
El teorema de Greenberg es una condición necesaria para que un gráfico plano contenga un ciclo hamiltoniano basado en las longitudes de ciclo de las caras. El resultado se usa ampliamente para construir gráficos no hamiltonianos con propiedades adicionales. Por ejemplo, se construyeron nuevos contraejemplos a la conjetura de Tate (que Tutt refutó en 1946). El teorema fue demostrado por el matemático letón Emanuel Grinberg en 1968.
Redacción
Sea G un gráfico plano finito con un ciclo hamiltoniano C con una incrustación plana fija. Denotar por ƒ k y g k el número de caras k -gonales de la incrustación que están dentro y fuera de C , respectivamente. Después
Esta fórmula es una simple consecuencia de la fórmula de Euler .
Un corolario de este teorema es que si un gráfico plano se puede incrustar de tal manera que todas las caras menos una sean congruentes con 2 módulo 3 y una cara no sea igual a 2 módulo 3, entonces el gráfico no es hamiltoniano. Por ejemplo, en el gráfico de la figura, todas las caras tienen 5 u 8 lados, y la cara exterior tiene 9 lados, por lo que cumple la condición del teorema y, por lo tanto, no es hamiltoniano. Para cualquier gráfico plano, las caras en las que el número de lados es congruente con 2 módulo 3 dan 0 módulo 3 a la suma en el teorema de Greenberg, ya que el factor k − 2 en su suma se anula. Sin embargo, las otras caras dan un valor distinto de cero módulo 3, independientemente de si están dentro o fuera del ciclo hamiltoniano. Y si solo hay una de esas caras, la suma total no puede ser cero y el gráfico debe ser no hamiltoniano.
Aplicaciones
Greenberg usó su teorema para encontrar gráficos poliédricos cúbicos no hamiltonianos con alta conectividad de borde cíclico. La conectividad de borde cíclico de un gráfico es el número más pequeño de bordes que se pueden eliminar para que el gráfico restante contenga más de un componente cíclico. El gráfico Tutta de 46 vértices y los gráficos poliédricos no hamiltonianos cúbicos más pequeños derivados de él tienen una conexión de borde cíclica de tres. Greenberg usó su teoría para encontrar un gráfico poliédrico cúbico no hamiltoniano con 44 vértices, 24 caras y una conexión de arista cíclica de cuatro, así como otro ejemplo (que se muestra en la figura) con 46 vértices, 25 caras y una conexión de arista cíclica de cinco, la conexión de borde máxima posible para gráficos planos cúbicos que no sean K 4 . En el ejemplo anterior, todas las caras delimitadas tienen cinco u ocho aristas, en ambos casos el número de caras es congruente con 2 módulo 3, pero la cara exterior tiene nueve aristas, lo que da una contribución distinta de cero a la fórmula del teorema de Greenberg módulo 3. Por tanto, la gráfica no puede ser hamiltoniana.
El teorema de Greenberg también se usa para encontrar grafos planos hipo-hamiltonianos , nuevamente mediante la construcción de un gráfico en el que todas las caras tienen un número de aristas congruentes con 2 módulo 3 [1] [2] . Thomassen [3] usó el teorema de una manera un poco más complicada para encontrar un gráfico hipohamiltoniano cúbico plano: el gráfico que construyó incluía una cara de 4 aristas adyacente a una cara de 7 aristas, y todas las demás caras tenían cinco u ocho aristas. Para que la gráfica satisfaga el teorema de Greenberg, una de las caras con 4 o 7 aristas tendría que estar separada de las otras cuatro, lo cual es imposible.
Restricciones
Hay gráficos planos no hamiltonianos en los que todas las caras tienen cinco u ocho lados. Para estos gráficos, la fórmula de Greenberg, tomada módulo tres, siempre satisface cualquier partición de las caras en dos subconjuntos, lo que evita que el teorema se use para probar la no hamiltonianidad en este caso ( Zaks 1977 ).
Es imposible usar el teorema de Greenberg para encontrar contraejemplos a la conjetura de Barnett de que cualquier gráfico poliédrico bipartito cúbico es hamiltoniano. En estos gráficos, siempre hay una partición de caras en dos subconjuntos que satisfacen el teorema de Greenberg, independientemente de que sea hamiltoniano ( Krooss 2004 ).
Notas
Literatura
- E. Ya. Grinberg. Gráficos planos homogéneos de grado tres sin ciclos hamiltonianos. // Latv. Matemáticas. anuario. - T. 4 . - S. 51-58. .
- André Krooss. Die Barnette'sche Vermutung und die Grinberg'sche Formel (alemán) // Analele Universităţii din Craiova. Seria Mathematica-Informatica. - 2004. - Bd. 31 . — S. 59–65 .
- José Malkevitch. Fórmula poliédrica de Euler: Parte II . - American Mathematical Society , 2005. - (Columna destacada).
- Carsten Thomassen. Grafos planares e infinitos hipohamiltonianos e hipotrazables // Matemáticas discretas . - 1976. - T. 14 , núm. 4 . — S. 377–389 . - doi : 10.1016/0012-365X(76)90071-6 .
- Carsten Thomassen. Gráficos cúbicos planos hipo-hamiltonianos e hipotrazables // Journal of Combinatorial Theory . - 1981. - T. 30 , núm. 1 . — págs. 36–44 . -doi : 10.1016 / 0095-8956(81)90089-7 .
- Gabor Wiener, Makoto Araya. La pregunta definitiva . - 2009. - arXiv : 0904.3012 .
- WT Tutte . Capítulo 2: Caballeros Errantes // Teoría de grafos tal como la he conocido. - Nueva York: The Clarendon Press Oxford University Press, 1998. - V. 11. - (Oxford Lecture Series in Mathematics and its Applications). - ISBN 0-19-850251-6 .
- José Zaks. Gráficos no hamiltonianos no grinbergianos // Matemáticas discretas . - 1977. - T. 17 , núm. 3 . — S. 317–321 . - doi : 10.1016/0012-365X(77)90165-0 .