Pósa's Theorem

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

Let  be a simple graph with  graph vertices.

1. If, for every  in , the number of graph vertices of vertex degree not exceeding  is less than , and

2. If, for  odd, the number of graph vertices with vertex degree not exceeding  is less than or equal to ,

then  contains a Hamiltonian cycle.

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

1. For all integers  with , the number of graph vertices of vertex degree not exceeding  is less than ,

2. The number of points of degree not exceeding  does not exceed .

Pósa (1963) generalized a result of Dirac by proving that every finite simple graph  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.  has a Hamiltonian line containing all edges of given disjoint paths (Theorem 1),

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

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

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. "-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.