Pancyclism and small cycles in graphs

• Volume: 16, Issue: 1, page 27-40
• ISSN: 2083-5892

top

Abstract

top
We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), ${d}_{C}\left(u,v\right)$ being the distance of u and v on a hamiltonian cycle of G.

How to cite

top

Ralph Faudree, et al. "Pancyclism and small cycles in graphs." Discussiones Mathematicae Graph Theory 16.1 (1996): 27-40. <http://eudml.org/doc/270583>.

@article{RalphFaudree1996,
abstract = {We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.},
author = {Ralph Faudree, Odile Favaron, Evelyne Flandrin, Hao Li},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cycle; hamiltonian; pancyclic; hamiltonian path; distance; hamiltonian cycle},
language = {eng},
number = {1},
pages = {27-40},
title = {Pancyclism and small cycles in graphs},
url = {http://eudml.org/doc/270583},
volume = {16},
year = {1996},
}

TY - JOUR
AU - Ralph Faudree
AU - Odile Favaron
AU - Evelyne Flandrin
AU - Hao Li
TI - Pancyclism and small cycles in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1996
VL - 16
IS - 1
SP - 27
EP - 40
AB - We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.
LA - eng
KW - cycle; hamiltonian; pancyclic; hamiltonian path; distance; hamiltonian cycle
UR - http://eudml.org/doc/270583
ER -

References

top
1. [1] D. Amar, E. Flandrin, I. Fournier and A. Germa, Pancyclism in hamiltonian graphs, Discrete Math. 89 (1991) 111-131, doi: 10.1016/0012-365X(91)90361-5. Zbl0727.05039
2. [2] A. Benhocine and A. P. Wojda, The Geng-Hua Fan conditions for pancyclic or hamilton-connected graphs, J. Combin. Theory (B) 42 (1987) 167-180, doi: 10.1016/0095-8956(87)90038-4. Zbl0613.05038
3. [3] J.A. Bondy, Pancyclic graphs. I., J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5. Zbl0183.52301
4. [4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan Press, 1976). Zbl1226.05083
5. [5] R. Faudree, O. Favaron, E. Flandrin and H. Li, The complete closure of a graph, J. Graph Theory 17 (1993) 481-494, doi: 10.1002/jgt.3190170406. Zbl0782.05046
6. [6] E.F. Schmeichel and S.L. Hakimi, Pancyclic graphs and a conjecture of Bondy and Chvátal, J. Combin. Theory (B) 17 (1974) 22-34, doi: 10.1016/0095-8956(74)90043-4. Zbl0268.05120
7. [7] 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
8. [8] R.H. Shi, The Ore-type conditions on pancyclism of hamiltonian graphs, personal communication. Zbl0729.05031

top

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.