Skip to main content
Article
Cycle Extendability in Graphs and Digraphs
Linear Algebra and its Applications
  • LeRoy B. Beasley, Utah State University
  • David E. Brown, Utah State University
Document Type
Article
Publisher
Elsevier
Publication Date
1-1-2011
Abstract

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.

Citation Information
Beasley, L.B., D. E. Brown, Cycle Extendability in Graphs and Digraphs, Linear Algebra and its Applications, 435:7 (2011) 15131519.