A note on a new condition implying pancyclism

Evelyne Flandrin; Hao Li; Antoni Marczyk; Mariusz Woźniak

Discussiones Mathematicae Graph Theory (2001)

  • Volume: 21, Issue: 1, page 137-143
  • ISSN: 2083-5892

Abstract

top
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 K n / 2 , n / 2 .

How to cite

top

Evelyne Flandrin, et al. "A note on a new condition implying pancyclism." Discussiones Mathematicae Graph Theory 21.1 (2001): 137-143. <http://eudml.org/doc/270348>.

@article{EvelyneFlandrin2001,
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 $K_\{n/2,n/2\}$.},
author = {Evelyne Flandrin, Hao Li, Antoni Marczyk, Mariusz Woźniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hamiltonian graphs; pancyclic graphs; cycles; Hamiltonian; pancyclic},
language = {eng},
number = {1},
pages = {137-143},
title = {A note on a new condition implying pancyclism},
url = {http://eudml.org/doc/270348},
volume = {21},
year = {2001},
}

TY - JOUR
AU - Evelyne Flandrin
AU - Hao Li
AU - Antoni Marczyk
AU - Mariusz Woźniak
TI - A note on a new condition implying pancyclism
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 1
SP - 137
EP - 143
AB - 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 $K_{n/2,n/2}$.
LA - eng
KW - hamiltonian graphs; pancyclic graphs; cycles; Hamiltonian; pancyclic
UR - http://eudml.org/doc/270348
ER -

References

top
  1. [1] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5. Zbl0183.52301
  2. [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. Zbl0331.05138
  3. [3] J.A. Bondy and U.S.A. Murty, Graph Theory with Applications (Elsevier, North Holland, New York, 1976). 
  4. [4] V. Chvátal, On Hamilton's ideals, J. Combin. Theory 12 (B) (1972) 163-168. Zbl0213.50803
  5. [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. Zbl0047.17001
  6. [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. Zbl0551.05048
  7. [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. Zbl0879.05042
  8. [8] O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928. 
  9. [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. Zbl0607.05050
  10. [10] Z. Skupień, private communication. 
  11. [11] R. Zhu, Circumference in 2-connected graphs, Qu-Fu Shiyuan Xuebao 4 (1983) 8-9. 
  12. [12] L. Zhenhong, G. Jin and C. Wang, Two sufficient conditions for pancyclic graphs, Ars Combinatoria 35 (1993) 281-290. Zbl0788.05059

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.