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