DMGT

Discussiones Mathematicae Graph Theory 16(1) (1996) 27-40
DOI: https://doi.org/10.7151/dmgt.1021

PANCYCLISM AND SMALL CYCLES IN GRAPHS

Ralph Faudree

Department of Mathematical Sciences, University of Memphis
Memphis, TN 38152, USA

Odile Favaron
Evelyne Flandrin
Hao Li

L.R.I., URA 410 du C.N.R.S. Bât. 490, Université de Paris-sud
91405-Orsay cedex, France.

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 (d_C(u,v)+1, [(n+19)/13]), d_C(u,v) being the distance of u and v on a hamiltonian cycle of G.

Keywords: cycle, hamiltonian, pancyclic.

1991 Mathematics Subject Classification: 05C38.

References

[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.
[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.
[3]	J.A. Bondy, Pancyclic graphs. I., J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
[4]	J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan Press, 1976).
[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.
[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.
[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.
[8]	R.H. Shi, The Ore-type conditions on pancyclism of hamiltonian graphs, personal communication.