DMGT

Discussiones Mathematicae Graph Theory 27(1) (2007) 29-38
DOI: https://doi.org/10.7151/dmgt.1341

NEW SUFFICIENT CONDITIONS FOR HAMILTONIAN AND PANCYCLIC GRAPHS

Ingo Schiermeyer

Fakultät für Mathematik und Informatik
Technische Universität Bergakademie Freiberg
09596 Freiberg, Germany

Mariusz Woźniak

Faculty of Applied Mathematics
AGH University of Science and Technology
Mickiewicza 30, 30-059 Kraków, Poland

Abstract

For a graph G of order n we consider the unique partition of its vertex set V(G) = A∪B with A = {v ∈ V(G):d(v) ≥ n/2} and B = {v ∈ V(G):d(v) < n/2}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.

Keywords: hamiltonian graphs, pancyclic graphs, closure.

2000 Mathematics Subject Classification: 05C38, 05C45.

References

[1]	A. Ainouche and N. Christofides, Semi-independence number of a graph and the existence of hamiltonian circuits, Discrete Appl. Math. 17 (1987) 213-221, doi: 10.1016/0166-218X(87)90025-4.
[2]	J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
[3]	J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-136, doi: 10.1016/0012-365X(76)90078-9.
[4]	J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier North Holland, New York, 1976).
[5]	G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
[6]	R.J. Faudree, R.Häggkvist and R.H. Schelp, Pancyclic graphs - connected Ramsey number, Ars Combin. 11 (1981) 37-49.
[7]	E. Flandrin, H. Li, A. Marczyk and M. Woźniak, A note on a new condition implying pancyclism, Discuss. Math. Graph Theory 21 (2001) 137-143, doi: 10.7151/dmgt.1138.
[8]	G. Jin, Z. Liu and C. Wang, Two sufficient conditions for pancyclic graphs, Ars Combinatoria 35 (1993) 281-290.
[9]	O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
[10]	E.F. Schmeichel and S.L. Hakimi, A cycle structure theorem for hamiltonian graphs, J. Combin. Theory (B) 45 (1988) 99-107, doi: 10.1016/0095-8956(88)90058-5.

Received 1 June 2005
Revised 28 April 2006