On Hamiltonicity of \{claw, net\}-free graphs
From MaRDI portal
Publication:2433732
DOI10.1016/J.DISC.2006.04.022zbMATH Open1106.05055arXivmath/0607234OpenAlexW2055925267MaRDI QIDQ2433732FDOQ2433732
Authors: Alexander Kelmans 
Publication date: 30 October 2006
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: An st-path is a path with the end-vertices s and t. An s-path is a path with an end-vertex s. The results of this paper include necessary and sufficient conditions for a {claw, net}-free graph G with given two different vertices s, t and an edge e to have (1)a Hamiltonian s-path, (2) a Hamiltonian st-path, (3) a Hamiltonian s- and st-paths containing edge e when G has connectivity one, and (4) a Hamiltonian cycle containing e when G is 2-connected. These results imply that a connected {claw, net}-free graph has a Hamiltonian path and a 2-connected {claw, net}-free graph has a Hamiltonian cycle [D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden Subgraphs and the Hamiltonian Theme, in The Theory and Application of Graphs (Kalamazoo, Mich., 1980$), Wiley, New York (1981) 297--316.] Our proofs of (1)-(4) are shorter than the proofs of their corollaries in [D. Duffus, R.J. Gould, M.S. Jacobson] and provide polynomial-time algorithms for solving the corresponding Hamiltonicity problems. Keywords: graph, claw, net, {claw, net}-free graph, Hamiltonian path, Hamiltonian cycle, polynomial-time algorithm.
Full work available at URL: https://arxiv.org/abs/math/0607234
Recommendations
Cites Work
- Claw-free graphs---a survey
- On a closure concept in claw-free graphs
- On graph closures
- Title not available (Why is that?)
- Hamiltonicity in claw-free graphs
- Title not available (Why is that?)
- The struction of a graph: Application to CN-free graphs
- On Hamiltonicity of \{claw, net\}-free graphs
- Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs
Cited In (16)
- Title not available (Why is that?)
- On Hamiltonian claw-free graphs
- On independent vertex sets in subclasses of apple-free graphs
- Title not available (Why is that?)
- A note on Hamiltonicity of generalized net-free graphs of large diameter
- On uniquely Hamiltonian claw-free and triangle-free graphs
- On Hamiltonicity of \{claw, net\}-free graphs
- Hamiltonicity in claw-free graphs
- Finding Hamiltonian cycles in \(\{\)quasi-claw, \(K_{1,5},K_{1,5} + e\}\)-free graphs with bounded Dilworth numbers
- Mengerian properties, hamiltonicity, and claw‐free graphs
- Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs
- On distance-3 matchings and induced matchings
- Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs
- On distance-3 matchings and induced matchings
- Clique covering and degree conditions for Hamiltonicity in claw-free graphs
- Title not available (Why is that?)
This page was built for publication: On Hamiltonicity of \{claw, net\}-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433732)
