Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1016/0012-365X(93)E0193-8 | Discrete Mathematics |
Keywords | Field | DocType |
degree condition,cycle extendability,hamiltonian cycle | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
141 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
3 | 0.69 | 2 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
R. J. Faudree | 1 | 174 | 38.15 |
R. J. Gould | 2 | 23 | 4.92 |
M. S. Jacobson | 3 | 198 | 40.79 |
L. M. Lesniak | 4 | 44 | 8.23 |