In 1962, Pósa conjectured that contains a square of a Hamiltonian
cycle if
(Erdős 1964, p. 159; Komlós et al. 1996), where a graph contains the square
of a Hamiltonian cycle if there is a Hamiltonian
cycle
such that ,
for ,
2, ..., .
Komlós et al. (1996) proved that there exists a natural number such that if a graph has order and minimum vertex
degree at least ,
then
contains the square of a Hamiltonian cycle. This proved Pósa's conjecture
(Erdős 1964) for sufficiently large . Kierstead and Quintana (1998) proved Pósa's conjecture
for graphs
containing a 4-clique .
The conjecture was generalized by Seymour (1974) to state that if , then contains the th power of a Hamiltonian
cycle (Komlós et al. 1996).
Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Dirac, G. A.
"Some Theorems on Abstract Graphs." Proc. London Math. Soc.2,
69-81, 1952.Erdős, P. "Problem 9." In Theory of Graphs
and Its Applications, Proceedings of the Symposium held in Smolenice in June 1963
(Ed. M. Fiedler). Prague, Czechoslovakia: Publishing House of the Czechoslovak
Academy of Sciences, p. 159, 1964.Fan, G. and Kierstead, H. A.
"Hamiltonian Square-Paths." J. Combin. Theory Ser. B67,
167-182, 1996.Kierstead, H. A. and Quintana, J. "Square Hamiltonian
Cycles in Graphs with Maximal 4-Cliques." Disc. Math.178, 81-92,
1998.Komlós, J.; Sárkőzy, G. N.; and Szemerédi,
E. "On the Square of a Hamiltonian Cycle in Dense Graphs." In Random
Structures Algorithms9, 193-211, 1996.Seymour, P. Problem
Section in Combinatorics:
Proceedings of the British Combinatorial Conference, 1973 (Ed. T. P. McDonough
and V. C. Mavron). Cambridge, England: Cambridge University Press, pp. 201-202,
1974.
for a graph 
on 
nodes, then 
contains a Hamiltonian cycle (Bollobás
1978, Komlós et al. 1996).
contains a square of a Hamiltonian
cycle if 
(Erdős 1964, p. 159; Komlós et al. 1996), where a graph 
contains the square
of a Hamiltonian cycle if there is a Hamiltonian
cycle 
such that 
,
for 
,
2, ..., 
.
such that if a graph 
has order 
and minimum vertex
degree at least 
,
then 
contains the square of a Hamiltonian cycle. This proved Pósa's conjecture
(Erdős 1964) for sufficiently large 
. Kierstead and Quintana (1998) proved Pósa's conjecture
for graphs 
containing a 4-clique 
.
, then 
contains the 
th power of a Hamiltonian
cycle (Komlós et al. 1996).
