Cycle Extendability of Hamiltonian Strongly Chordal Graphs
Guozhen Rong, Wenjun Li, Jianxin Wang, Yongjie Yang · SIAM Journal on Discrete Mathematics · 2021
In 1990, Hendry conjectured that all Hamiltonian chordal graphs are cycle extendable. After a series of papers confirming the conjecture for a number of graph classes, the conjecture is yet refuted by Lafond and Seamone in 2015. Given that their counterexamples are not strongly chordal graphs and they are all only 2-connected, Lafond and Seamone asked the following two questions: (1) Are Hamiltonian strongly chordal graphs cycle extendable? (2) Is there an integer $k$ such that all $k$-connected Hamiltonian chordal graphs are cycle extendable? Later, a conjecture stronger than Hendry's is proposed. In this paper, we resolve all these questions in the negative. On the positive side, we add to the list of cycle-extendable graphs two more graph classes, namely, Hamiltonian 4-fan-free chordal graphs, where every induced $K_5 - e$ has true twins, and Hamiltonian $\{4{\sc -fan}, \overline{A} \}$-free chordal graphs.