Pancyclicity of claw-free hamiltonian graphs

Trommel, H. and Veldman, H.J. and Verschut, A. (1999) Pancyclicity of claw-free hamiltonian graphs. Discrete Mathematics, 197-198 . pp. 781-789. ISSN 0012-365X

PDF
Restricted to UT campus only: Request a copy
407Kb

Abstract:	A graph G on n vertices is called subpancyclic if it contains cycles of every length k with 3 ≤ k ≤ c(G), where c(G) denotes the length of a longest cycle in G; if moreover c(G) = n, then G is called pancyclic. By a result of Flandrin et al. a claw-free graph (on at least 35 vertices) with minimum degree at least 1/3(n-2) is pancyclic. This degree bound is best possible. We prove that for a claw-free graph to be subpancyclic we only need the degree condition δ > √3n + 1 − 2. Again, this degree bound is best possible. It follows directly that under the same condition a hamiltonian claw-free graph is pancyclic.
Item Type:	Article
Copyright:	© 1999 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/74021
Official URL:	http://dx.doi.org/10.1016/S0012-365X(99)90147-4
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 140565