Hamiltonian chordal graphs are not cycle extendible
classification
🧮 math.CO
cs.DM
keywords
cyclechordalhamiltonianverticescounterexamplesextendiblegraphslength
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.