The Pósa condition for a finite undirected graph having vertices requires that, if the degrees of the vertices in increasing order as
then for each index the inequality is satisfied.
Pósa's theorem states that if a finite undirected graph satisfies the Pósa condition, then that graph has a Hamiltonian cycle in it.
References
Pósa, L. (1962), "A theorem concerning Hamilton lines", Magyar Tud. Akad. Mat. Kutató Int. Közl., 7: 225–226, MR 0184876
Katona–Recski–Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003, (Hungarian undergraduate level course book).
Kronk, Hudson V. (1969), "Generalization of a theorem of Pósa", Proceedings of the American Mathematical Society, 21: 77–78, doi:10.2307/2036861, MR 0237377
Kühn, Daniela; Osthus, Deryk; Treglown, Andrew (2009), "Degree sequences forcing Hamilton cycles in directed graphs", European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electron. Notes Discrete Math., vol. 34, Amsterdam: Elsevier Sci. B. V., pp. 347–351, doi:10.1016/j.endm.2009.07.057, MR 2591466
pósa, theorem, confused, with, erdős, pósa, theorem, graph, theory, sufficient, condition, existence, hamiltonian, cycle, based, degrees, vertices, undirected, graph, implies, other, degree, based, sufficient, conditions, dirac, theorem, hamiltonian, cycles, t. Not to be confused with the Erdos Posa theorem Posa s theorem in graph theory is a sufficient condition for the existence of a Hamiltonian cycle based on the degrees of the vertices in an undirected graph It implies two other degree based sufficient conditions Dirac s theorem on Hamiltonian cycles and Ore s theorem Unlike those conditions it can be applied to graphs with a small number of low degree vertices It is named after Lajos Posa a protege of Paul Erdos born in 1947 who discovered this theorem in 1962 The Posa condition for a finite undirected graph G displaystyle G having n displaystyle n vertices requires that if the degrees of the n displaystyle n vertices in increasing order as d 1 d 2 d n displaystyle d 1 leq d 2 leq leq d n then for each index k lt n 2 displaystyle k lt n 2 the inequality k lt d k displaystyle k lt d k is satisfied Posa s theorem states that if a finite undirected graph satisfies the Posa condition then that graph has a Hamiltonian cycle in it References EditPosa L 1962 A theorem concerning Hamilton lines Magyar Tud Akad Mat Kutato Int Kozl 7 225 226 MR 0184876 Katona Recski Szabo A szamitastudomany alapjai Typotex Budapest 2003 Hungarian undergraduate level course book Kronk Hudson V 1969 Generalization of a theorem of Posa Proceedings of the American Mathematical Society 21 77 78 doi 10 2307 2036861 MR 0237377 Kuhn Daniela Osthus Deryk Treglown Andrew 2009 Degree sequences forcing Hamilton cycles in directed graphs European Conference on Combinatorics Graph Theory and Applications EuroComb 2009 Electron Notes Discrete Math vol 34 Amsterdam Elsevier Sci B V pp 347 351 doi 10 1016 j endm 2009 07 057 MR 2591466 Yin Jian Hua Zhang Yue 2011 Posa condition and nowhere zero 3 flows Discrete Mathematics 311 12 897 907 doi 10 1016 j disc 2011 02 023 MR 2787300External links EditWeisstein Eric W Posa s Theorem MathWorld About the Posa theorem Retrieved from https en wikipedia org w index php title Posa 27s theorem amp oldid 1032330095, wikipedia, wiki, book, books, library,
