
arXiv: 2007.04698
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$-\textsc{fan}-free chordal graphs where every induced $K_5 - e$ has true twins, and Hamiltonian $\{4\textsc{-fan}, \overline{A} \}$-free chordal graphs.
14 pages, 6 figures. [v3]: To appear in SIDMA
FOS: Computer and information sciences, Eulerian and Hamiltonian graphs, Discrete Mathematics (cs.DM), chordal graphs, cycle extendability, Graph algorithms (graph-theoretic aspects), Hamiltonian graphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Eulerian and Hamiltonian graphs, Discrete Mathematics (cs.DM), chordal graphs, cycle extendability, Graph algorithms (graph-theoretic aspects), Hamiltonian graphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
