TOPICS
Search

Pósa's Conjecture


Dirac (1952) proved that if the minimum vertex degree delta(G)>=n/2 for a graph G on n>=3 nodes, then G contains a Hamiltonian cycle (Bollobás 1978, Komlós et al. 1996).

In 1962, Pósa conjectured that G(V,E) contains a square of a Hamiltonian cycle if delta(G)>=2n/3 (Erdős 1964, p. 159; Komlós et al. 1996), where a graph G(V,E) contains the square of a Hamiltonian cycle if there is a Hamiltonian cycle H=(x_1,x_2,...,x_n,x_(n+1)=x_1) such that (x_i,x_(i+2)) in E(G), for i=1, 2, ..., n.

Komlós et al. (1996) proved that there exists a natural number n_0 such that if a graph G has order n>=n_0 and minimum vertex degree at least 2n/3, then G contains the square of a Hamiltonian cycle. This proved Pósa's conjecture (Erdős 1964) for sufficiently large n. Kierstead and Quintana (1998) proved Pósa's conjecture for graphs G containing a 4-clique K_4.

The conjecture was generalized by Seymour (1974) to state that if delta(G)>=kn/(k+1), then G contains the kth power of a Hamiltonian cycle (Komlós et al. 1996).


See also

Hamiltonian Cycle, Pósa's Theorem, Seymour Conjecture

Explore with Wolfram|Alpha

References

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. B 67, 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 Algorithms 9, 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.

Referenced on Wolfram|Alpha

Pósa's Conjecture

Cite this as:

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

Subject classifications