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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1341,
author = {Ingo Schiermeyer and Mariusz Wo\'zniak},
title = {New sufficient conditions for hamiltonian and pancyclic graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {27},
year = {2007},
pages = {29-38},
zbl = {1134.05048},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1341}
}
Ingo Schiermeyer; Mariusz Woźniak. New sufficient conditions for hamiltonian and pancyclic graphs. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 29-38. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1341/
[000] [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.
[001] [2] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5. | Zbl 0183.52301
[002] [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. | Zbl 0331.05138
[003] [4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier North Holland, New York, 1976). | Zbl 1226.05083
[004] [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. | Zbl 0047.17001
[005] [6] R.J. Faudree, R.Häggkvist and R.H. Schelp, Pancyclic graphs - connected Ramsey number, Ars Combin. 11 (1981) 37-49. | Zbl 0485.05038
[006] [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. | Zbl 0989.05064
[007] [8] G. Jin, Z. Liu and C. Wang, Two sufficient conditions for pancyclic graphs, Ars Combinatoria 35 (1993) 281-290. | Zbl 0788.05059
[008] [9] O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
[009] [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. | Zbl 0607.05050