✦ LIBER ✦

Cycle extendability in graphs and digraphs

✍ Scribed by LeRoy B. Beasley; David E. Brown

Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 201 KB
Volume: 435
Category: Article
ISSN: 0024-3795
DOI: 10.1016/j.laa.2010.04.038

No coin nor oath required. For personal study only.

✦ Synopsis

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 Hamiltonian graph. Hendry's conjecture in this case is that every k × k principle submatrix of A that dominates a full cycle permutation k × k matrix is a principle submatrix of a (k + 1) × (k + 1) principle submatrix of A that dominates a (k + 1) × (k + 1) full cycle permutation matrix. This article generalizes the concept of cycle extendability to S-extendable; that is, with S ⊆ {1, 2, . . . , n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i ∈ S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.

📜 SIMILAR VOLUMES

Cycle packings in graphs and digraphs

✍ Jennifer J. Quinn 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 196 KB

A cycle packing in a (directed) multigraph is a vertex disjoint collection of (directed) elementary cycles. If D is a demiregular multidigraph we show that the arcs of D can be partitioned into Ai. cycle packings --where Ain is the maximum indegree of a vertex in D. We then show that the maximum len

Paths and cycles in extended and decompo

Paths and cycles in extended and decomposable digraphs

✍ Jørgen Bang-Jensen; Gregory Gutin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 835 KB

We consider digraphs --called extended locally semicomplete digraphs, or extended LSD's, for short --that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. We characterize Hamiltonian extended LSD's as well as extended LSD's containing Hamiltonian path

Extending cycles in graphs

✍ George R.T. Hendry 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 901 KB

## A cycle C in a graph G is extendable if there exists a cycle C' in G such that V(C) E V(C') and jV(C')l = IV(C) 1 + 1. A graph G is cycle extendable if G has at least one cycle and every nonhamiltonian cycle is extendable. A graph G of order p 2 3 has a pancyclic ordering if its vertices can be

Extending cycles in directed graphs

✍ George R.T Hendry 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 536 KB

Well-covered graphs and extendability

✍ Nathaniel Dean; Jennifer Zito 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 928 KB

Degree conditions and cycle extendabilit

Degree conditions and cycle extendability

✍ R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 664 KB

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