Originator: George Hendry (presented by Lesley Wiglesworth - REGS 2007)
Definitions: A graph is chordal if it has no induced subgraph that is a cycle of length at least 4. A graph G is cycle-extendible if for every non-spanning cycle C, there is a vertex v outside V(C) such that G has a cycle with vertex set V(C)∪{v} (nothing is required about the order of the vertices on the longer cycle).
Background: A graph is chordal if and only if every induced subgraph has a simplicial vertex (a vertex whose neighborhood is a clique) [D]. Therefore, every cycle has a "triangular chord" enabling a vertex to be skipped, thus "reducing" to a cycle with one less vertex.
Conjecture (Hendry [H]): Every chordal Hamiltonian graph is cycle-extendible.
Comments: Jiang [J] proved the conjecture for planar graphs. [AS] and [CFGJ] independently proved it for interval graphs in neighboring papers in the same journal issue, the former using properties of interval graphs and the latter using toughness.
References:
[AS] Abueida, Atif; Sritharan, R. Cycle extendability and Hamiltonian cycles in
chordal graph classes. SIAM J. Discrete Math. 20 (2006), no. 3, 669--681.
[CFGJ] Chen, Guantao; Faudree, Ralph J.; Gould, Ronald J.; Jacobson, Michael S.;
Cycle extendability of Hamiltonian interval graphs.
SIAM J. Discrete Math. 20 (2006), no. 3, 682--689.
[D] Dirac, G. A.; On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg 25 1961 71--76.
[H] Hendry, George R. T.; Extending cycles in graphs. Discrete Math. 85
(1990), no. 1, 59--72.
[J] Jiang, Tao; Planar Hamiltonian chordal graphs are cycle extendable.
Kleitman and combinatorics: a celebration (Cambridge, MA, 1999). Discrete Math.
257 (2002), no. 2-3, 441--444.