On Hamiltonian properties of K₁, r-free split graphs

DOI10.1016/J.DISC.2023.113402MaRDI QIDQ6041859zbMATH OpenOpenAlexFDO

Authors Xia Liu, Sulin Song, Mingquan Zhan, Hong-Jian Lai

Publication date 15 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2023.113402

zbMATH Keywords

\(K_{1, r}\)-free graphsfully cycle extendableHamiltonian cyclessplit graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

For \(r\geq 3\), a graph \(G\) is \(K_{1, r}\)-free if \(G\) does not have an induced subgraph isomorphic to \(K_{1, r}\). A graph \(G\) is fully cycle extendable if every vertex in \(G\) lies on a cycle of length 3 and every non-Hamiltonian cycle in \(G\) is extendable. A connected graph \(G\) is a split graph if the vertex set of \(G\) can be partitioned into a clique and a stable set. The authors introduce a certain type of alternating paths in the study of Hamiltonian properties of split graphs and prove that a split graph \(G\) is Hamiltonian if and only if \(G\) is fully cycle extendable. As a result, for \(r\in\{3, 4\}\), every \(r\)-connected \(K_{1, r}\)-free split graph is Hamilton-connected and every \((r-1)\)-connected \(K_{1,r}\)-free split graph is fully cycle extendable.

Recommendations

• The Hamiltonian properties in \(K_{1,r}\)-free split graphs
• A note on hamiltonian cycles in \(K_{1,r}\)-free graphs
• scientific article; zbMATH DE number 1161288
• Hamiltonicity for K_{1, r}‐free graphs
• Highly Hamiltonian \(K_{1,3}P_4\)-free graphs

Cites work

• A note on Hamiltonian split graphs
• Extending cycles in graphs
• Graph theory
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1424871 (Why is no real title available?)
• On the Burkard-Hammer condition for Hamiltonian split graphs
• Split graphs
• Split Graphs Having Dilworth Number Two
• The existence of a 2-factor in \(K_{1,n}\)-free graphs with large connectivity and large edge-connectivity
• The Hamiltonian properties in \(K_{1,r}\)-free split graphs
• Toughness, hamiltonicity and split graphs

Cited in

(6)

• The Hamiltonian properties in \(K_{1,r}\)-free split graphs
• Hamiltonian path in \(K_{1,t}\)-free split graphs -- a dichotomy
• Hamiltonicity in Split Graphs - A Dichotomy
• scientific article; zbMATH DE number 637321 (Why is no real title available?)
• Spanning connectivity of \(K_{1 , r}\)-free split graphs
• Spanning Fan-connectivity of \(K_{1,r}\)-free split graphs

This page was built for publication: On Hamiltonian properties of \(K_{1, r}\)-free split graphs

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