Pancyclism and small cycles in graphs

@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 -