Degree conditions and cycle extendability

A non-Hamiltonian cycle C in a graph G is extendable if there is a cycle C′ in G with V( C′) ⊃ V( C) with one more vertex than C. For any integer k ⩾ 0, a cycle C is k-chord extendable if it is extendable to the cycle C′ using at most k of the chords of the cycle C. It will be shown that if G is a g...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1995-06, Vol.141 (1), p.109-122
Main Authors: Faudree, R.J., Gould, R.J., Jacobson, M.S., Lesniak, L.M.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A non-Hamiltonian cycle C in a graph G is extendable if there is a cycle C′ in G with V( C′) ⊃ V( C) with one more vertex than C. For any integer k ⩾ 0, a cycle C is k-chord extendable if it is extendable to the cycle C′ using at most k of the chords of the cycle C. It will be shown that if G is a graph of order n, then δ( G) > 3 n/4 − 1 implies that any proper cycle is 0-chord extendable, δ( G) > 5 n/9 implies that any proper cycle is 1-chord extendable, and δ( G) > [ n/2] implies that any proper cycle is 2-chord extendable. Also, each of these results is sharp in the sense that the minimum degree condition cannot, in general, be lowered.
ISSN:0012-365X
1872-681X
DOI:10.1016/0012-365X(93)E0193-8