On the Burkard-Hammer condition for Hamiltonian split graphs

DOI10.1016/J.DISC.2005.03.008MaRDI QIDQ2484370zbMATH OpenOpenAlexFDO

Authors Ngo Dac Tan, Le Xuan Hung

Publication date 1 August 2005

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonian cycle

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75)

Review text

A graph \(G=(V,E)\) is called split graph if \(V\) splits into an independent set \(I\) and a clique \(C\). \textit{R. E. Burkard} and \textit{P. L. Hammer} [J.~Comb.\ Theory, Ser.~B 28, 245--248 (1980; Zbl 0403.05058)] gave a necessary condition for split graphs with \(| I| < | C| \) to be Hamiltonian. This condition is sufficient if \(\delta(G) \geq | I| -3\) and \(5 \neq | I| <| C| \). The case \(| I| =5\) is also settled.

Recommendations

• Combinatorial Geometry and Graph Theory
• A necessary condition for maximal nonhamiltonian Burkard-Hammer graphs
• Necessary conditions for Hamiltonian split graphs
• A classfication for maximal nonhamiltonian Burkard-Hammer graphs
• The completion of a classification for maximal nonhamiltonian Burkard-Hammer graphs

Cites work

• A note on Hamiltonian split graphs
• Combinatorial Geometry and Graph Theory
• Hamilton cycles in split graphs with large minimum degree
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3613062 (Why is no real title available?)
• scientific article; zbMATH DE number 3614694 (Why is no real title available?)
• scientific article; zbMATH DE number 3284075 (Why is no real title available?)
• Necessary conditions for Hamiltonian split graphs
• Toughness, hamiltonicity and split graphs

Cited in

(14)

• On the Hamiltonian and classification problems for some families of split graphs
• Necessary conditions for Hamiltonian split graphs
• The Hamiltonian properties in \(K_{1,r}\)-free split graphs
• The completion of a classification for maximal nonhamiltonian Burkard-Hammer graphs
• Hamiltonicity in Split Graphs - A Dichotomy
• A necessary condition for maximal nonhamiltonian Burkard-Hammer graphs
• A classfication for maximal nonhamiltonian Burkard-Hammer graphs
• scientific article; zbMATH DE number 4010558 (Why is no real title available?)
• On Hamiltonian properties of \(K_{1, r}\)-free split graphs
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
• Spanning connectivity of \(K_{1 , r}\)-free split graphs
• The chromaticity of complete split graphs
• Spanning Fan-connectivity of \(K_{1,r}\)-free split graphs
• A note on maximal nonhamiltonian Burkard-Hammer graphs

This page was built for publication: On the Burkard-Hammer condition for Hamiltonian split graphs

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