pith. sign in

arxiv: 1311.5863 · v2 · pith:FRSC6HHKnew · submitted 2013-11-22 · 🧮 math.CO · cs.DM

Hamiltonian chordal graphs are not cycle extendible

classification 🧮 math.CO cs.DM
keywords cyclechordalhamiltonianverticescounterexamplesextendiblegraphslength
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.