Cycle Extendability of Hamiltonian Strongly Chordal Graphs

DOI10.1137/20M1369920MaRDI QIDQ4959662zbMATH OpenOpenAlexFDO

Authors Guozhen Rong, Wen-Jun Li, Jianxin Wang, Yongjie Yang

Publication date 17 September 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.04698

zbMATH Keywords

chordal graphsHamiltonian graphscycle extendability

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Abstract: 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$- extsc{fan}-free chordal graphs where every induced $K_5-e$ has true twins, and Hamiltonian $4extsc-fan,overlineA$-free chordal graphs.

Recommendations

• Cycle Extendability and Hamiltonian Cycles in Chordal Graph Classes
• Cycle Extendability of Hamiltonian Interval Graphs
• Hamiltonian cycles in n‐extendable graphs
• Planar Hamiltonian chordal graphs are cycle extendable
• On the H-force number of Hamiltonian graphs and cycle extendability
• A cycle structure theorem for Hamiltonian graphs
• On Hamiltonian cycle extension in cubic Hamiltonian graphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamilton cycles in \(n\)-extendable bipartite graphs.
• An extremal problem for cycles in hamiltonian graphs

Cites work

• A characterization of ptolemaic graphs
• Characterizations of strongly chordal graphs
• Cycle Extendability and Hamiltonian Cycles in Chordal Graph Classes
• Cycle Extendability of Hamiltonian Interval Graphs
• Extending cycles in bipartite graphs
• Extending cycles in directed graphs
• Extending cycles in graphs
• Hamiltonian chordal graphs are not cycle extendable
• Hamiltonian spider intersection graphs are cycle extendable
• Leaf Powers and Their Properties: Using the Trees
• On cycle- and bi-cycle extendability in chordal and chordal bipartite graphs
• On rigid circuit graphs
• Planar Hamiltonian chordal graphs are cycle extendable
• Some Theorems on Abstract Graphs
• Some remarks about leaf roots
• Structure and linear time recognition of 3-leaf powers
• Well-partitioned chordal graphs: obstruction set and disjoint paths

Cited in

(9)

• Planar Hamiltonian chordal graphs are cycle extendable
• Cycle extendability in graphs and digraphs
• Further results on Hendry's Conjecture
• Cycle Extendability of Hamiltonian Interval Graphs
• On cycle- and bi-cycle extendability in chordal and chordal bipartite graphs
• Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
• Hamiltonian chordal graphs are not cycle extendable
• Cycle Extendability and Hamiltonian Cycles in Chordal Graph Classes
• Hamiltonian spider intersection graphs are cycle extendable

This page was built for publication: Cycle Extendability of Hamiltonian Strongly Chordal Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959662)