✦ LIBER ✦

Degree conditions and cycle extendability

✍ Scribed by R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 664 KB
Volume: 141
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0193-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 6(G)>3n/4-1 implies that any proper cycle is 0-chord extendable, 6(G)>5n/9 implies that any proper cycle is 1-chord extendable, and 6(G)>Ln/2 j 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.

📜 SIMILAR VOLUMES

Cycle extendability in graphs and digrap

Cycle extendability in graphs and digraphs

✍ LeRoy B. Beasley; David E. Brown 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 201 KB

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamilto

Hamilton cycle and Hamilton path extenda

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

✍ Štefko MiklaviČ; Primož Šparl 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is __n__‐__HC‐extendable__ if it contains a path of length __n__ and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is __weakly n__‐__HP‐

Edge proximity conditions for extendabil

Edge proximity conditions for extendability in cubic bipartite graphs

✍ R. E. L. Aldred; Bill Jackson 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB

## Abstract We show that a set __M__ of __m__ edges in a cyclically (3__m__ − 2)‐edge‐connected cubic bipartite graph is contained in a 1‐factor whenever the edges in __M__ are pairwise distance at least __f__(__m__) apart, where © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 112–120, 2007

Degree Sums and Covering Cycles

✍ Hikoe Enomoto; Atsushi Kaneko; Mekkia Kouider; Zsolt Tuza 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

## Abstract It is shown that if in a simple graph __G__ of order __n__ the sum of degrees of any three pairwise non‐adjacent vertices is at least __n__, then there are two cycles (or one cycle and an edge or a vertex) of __GF__ that contain all the vertices. © 1995 John Wiley & Sons, Inc.

A degree sum condition for longest cycle

A degree sum condition for longest cycles in 3-connected graphs

✍ Tomoki Yamashita 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 1 views

## Abstract For a graph __G__, we denote by __d__~__G__~(__x__) and κ(__G__) the degree of a vertex __x__ in __G__ and the connectivity of __G__, respectively. In this article, we show that if __G__ is a 3‐connected graph of order __n__ such that __d__~__G__~(__x__) + __d__~__G__~(__y__) + __d__~__

A degree sum condition on hamiltonian cy

A degree sum condition on hamiltonian cycles in balanced 3-partite graphs

✍ Kuniharu Yokomura 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 193 KB