Hamiltonian chordal graphs are not cycle extendible

In 1990, Hendry conjectured that every Hamiltonian chordal graph is cycle extendible; that is, the vertices of any non-Hamiltonian cycle are contained in a cycle of length one greater. We disprove this conjecture by constructing counterexamples on $n$ vertices for any $n \geq 15$. Furthermore, we show that there exist counterexamples where the ratio of the length of a non-extendible cycle to the total number of vertices can be made arbitrarily small. We then consider cycle extendibility in Hamiltonian chordal graphs where certain induced subgraphs are forbidden, notably $P_n$ and the bull.

No reviews yet.

No comments yet.