Condición suficiente para un ciclo hamiltoniano en un grafo, en función de los grados de sus vértices
El teorema de Pósa , en teoría de grafos , es una condición suficiente para la existencia de un ciclo hamiltoniano basado en los grados de los vértices en un grafo no dirigido. Implica otras dos condiciones suficientes basadas en grados, el teorema de Dirac sobre ciclos hamiltonianos y el teorema de Ore . A diferencia de esas condiciones, se puede aplicar a grafos con un pequeño número de vértices de bajo grado. Recibe su nombre en honor a Lajos Pósa , un protegido de Paul Erdős nacido en 1947, quien descubrió este teorema en 1962.
La condición de Pósa para un grafo finito no dirigido que tiene vértices requiere que, si los grados de los vértices en orden creciente como
entonces para cada índice se satisface la desigualdad .
El teorema de Pósa establece que si un grafo finito no dirigido satisface la condición de Pósa, entonces ese grafo tiene un ciclo hamiltoniano.
Referencias
- Pósa, L. (1962), "Un teorema sobre las líneas de Hamilton", Magyar Tud. Akád. Estera. Aeropuerto Internacional de Kutató. Kozl. , 7 : 225–226, SEÑOR 0184876
- Katona – Recski – Szabó: A számítástudomány alapjai , Typotex, Budapest, 2003, (libro de curso de pregrado en húngaro).
- Kronk, Hudson V. (1969), "Generalización de un teorema de Pósa", Actas de la American Mathematical Society , 21 : 77–78, doi :10.2307/2036861, MR 0237377
- Kühn, Daniela ; Osthus, Deryk ; Treglown, Andrew (2009), "Secuencias de grados que fuerzan ciclos de Hamilton en grafos dirigidos", European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009) , Electron. Notes Discrete Math., vol. 34, Ámsterdam: Elsevier Sci. BV, págs. 347–351, doi :10.1016/j.endm.2009.07.057, MR 2591466
- Yin, Jian-Hua; Zhang, Yue (2011), "Condición de posa y flujos de 3 flujos de cero en ninguna parte", Discrete Mathematics , 311 (12): 897–907, doi :10.1016/j.disc.2011.02.023, MR 2787300
Enlaces externos
