Download PDF - A note on a new condition implying pancyclismAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A note on a new condition implying pancyclism

Authors 1, 1, 2, 2

Affiliations

  1. LRI, Bât. 490, Université de Paris-Sud, 91405 Orsay, France
  2. Faculty of Applied Mathematics AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland

Abstract

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to Kn2,n2.

Keywords

ENG
hamiltonian graphs, pancyclic graphs, cycles

Bibliography

  1. J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
  2. 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.
  3. J.A. Bondy and U.S.A. Murty, Graph Theory with Applications (Elsevier, North Holland, New York, 1976).
  4. V. Chvátal, On Hamilton's ideals, J. Combin. Theory 12 (B) (1972) 163-168.
  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. G.H. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory (B) 37 (1984) 221-227, doi: 10.1016/0095-8956(84)90054-6.
  7. R. Faudree, O. Favaron, E. Flandrin and H. Li, Pancyclism and small cycles in graphs, Discuss. Math. Graph Theory 16 (1996) 27-40, doi: 10.7151/dmgt.1021.
  8. O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
  9. 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.
  10. Z. Skupień, private communication.
  11. R. Zhu, Circumference in 2-connected graphs, Qu-Fu Shiyuan Xuebao 4 (1983) 8-9.
  12. L. Zhenhong, G. Jin and C. Wang, Two sufficient conditions for pancyclic graphs, Ars Combinatoria 35 (1993) 281-290.
Discussiones Mathematicae Graph Theory
2001/21/1
Export to PBN, Opens in new tab
Pages:
137-143
Main language of publication
English
Received
2000-11-15
Accepted
2000-12-13
Published
2001

DOI: 10.7151/dmgt.1138

Exact and natural sciences