TOPICS
Search

Pósa's Theorem


There are several related theorems involving Hamiltonian cycles of graphs that are associated with Pósa.

Let G be a simple graph with n graph vertices.

1. If, for every k in 1<=k<(n-1)/2, the number of graph vertices of vertex degree not exceeding k is less than k, and

2. If, for n odd, the number of graph vertices with vertex degree not exceeding (n-1)/2 is less than or equal to (n-1)/2,

then G contains a Hamiltonian cycle.

Kronk (1969) generalized this result as follows. Let G be a simple graph with n graph vertices, and let 0<=k<=n-2. Then the following conditions are sufficient for G to be k-line Hamiltonian:

1. For all integers j with k+1<=j<(n+k-1)/2, the number of graph vertices of vertex degree not exceeding j is less than j-k,

2. The number of points of degree not exceeding (n+k-1)/2 does not exceed (n-k-1)/2.

Pósa (1963) generalized a result of Dirac by proving that every finite simple graph G with a sufficiently large valencies of all (or, in some cases, of almost all) vertices and with a sufficiently large number of vertices satisfies one of the following conditions.

1. G has a Hamiltonian line containing all edges of given disjoint paths (Theorem 1),

2. G has a circuit with a "large" number of vertices (Theorems 2 and 3), or

3. G has a "small" number of disjoint circuits containing all vertices of the graph (Theorems 4 and 5).


See also

Pósa's Conjecture

Explore with Wolfram|Alpha

References

Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bondy, J. A. "Cycles in Graphs." In Combinatorial Structures and their Applications: Proc. Calgary Internat. Conf., Calgary, Alberta, 1969. New York: Gordon and Breach, pp. 15-18, 1970.Dirac, G. A. "Some Theorems on Abstract Graphs." Proc. London Math. Soc. 2, 69-81, 1952.Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs." Ann. Comb. 2, 43-60, 1998.Kronk, H. V. "Variations on a Theorem of Pósa." In The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968). Berlin: Springer-Verlag, pp. 193-197, 1969.Lick, D. R. "n-Hamiltonian Connected Graphs." Duke Math. J. 37, 387-392, 1970.Marshall, C. W. Applied Graph Theory. New York: Wiley, 1971.Nash-Williams, C. St. J. A. "Hamiltonian Lines in Graphs Whose Vertices Have Sufficiently Large Valencies." In Combinatorial Theory and Its Applications, III (Proc. Colloq., Balatonfüred, 1969). Amsterdam, Netherlands: North-Holland, pp. 813-819, 1970.Nash-Williams, C. St. J. A. "Hamiltonian Lines in Infinite Graphs with Few Vertices of Small Valency." Aequationes Math. 7, 59-81, 1971.Pósa, L. "On the Circuits of Finite Graphs." Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 8, 355-361, 1963.

Referenced on Wolfram|Alpha

Pósa's Theorem

Cite this as:

Weisstein, Eric W. "Pósa's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PosasTheorem.html

Subject classifications