On Hamiltonicity of \{claw, net\}-free graphs

DOI10.1016/J.DISC.2006.04.022MaRDI QIDQ2433732zbMATH OpenOpenAlexFDO

Authors Alexander Kelmans

Publication date 30 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(CN\)-free graphHamiltonian cycleHamiltonian pathpolynomial-time algorithms

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

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.

Review text

A path with an endvertex \(s\) is called an \(s\)-path and likewise \(st\)-paths are ones with endvertices \(s\) and \(t\). Conditions are given that imply a \(CN\)-free graph, where \(C\) is a claw and \(N\) is a net, has \(s\)-paths and \(st\)-paths that are Hamiltonian. For example it is shown that if \(G\) is a graph of order at least \(3\) with \(\kappa(G) = 1\), then \(G\) has an \(st\)-path that is Hamiltonian if and only if \(s\) and \(t\) are inner vertices of different endblocks of \(G\). Similar results are given for \(s\)-paths and \(st\)-paths that contain a predetermined edge \(e\). Also, corresponding results are given for Hamiltonian cycles in a \(2\)-connected \(CN\)-free graph. These theorems generalize know results for the existence of Hamiltonian paths and cycles in \(CN\)-free graphs.

Recommendations

• Hamiltonicity in claw-free graphs
• A note on Hamiltonicity of generalized net-free graphs of large diameter
• Hamilton cycles in 3-connected claw-free and net-free graphs
• scientific article; zbMATH DE number 1420921
• Hamilton‐connected {claw,net}‐free graphs, II

Cites work

• Claw-free graphs---a survey
• Hamiltonicity in claw-free graphs
• scientific article; zbMATH DE number 3730183 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs
• On a closure concept in claw-free graphs
• On graph closures
• On Hamiltonicity of \{claw, net\}-free graphs
• The struction of a graph: Application to CN-free graphs

Cited in

(17)

• Finding Hamiltonian cycles in \(\{\)quasi-claw, \(K_{1,5},K_{1,5} + e\}\)-free graphs with bounded Dilworth numbers
• Hamiltonicity in claw-free graphs
• A note on Hamiltonicity of generalized net-free graphs of large diameter
• Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs
• On uniquely Hamiltonian claw-free and triangle-free graphs
• On Hamiltonicity of \{claw, net\}-free graphs
• Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs
• On distance-3 matchings and induced matchings
• Mengerian properties, hamiltonicity, and claw‐free graphs
• scientific article; zbMATH DE number 1159768 (Why is no real title available?)
• scientific article; zbMATH DE number 1420921 (Why is no real title available?)
• scientific article; zbMATH DE number 5026868 (Why is no real title available?)
• Clique covering and degree conditions for Hamiltonicity in claw-free graphs
• On Hamiltonian claw-free graphs
• Graph grabbing game on graphs with forbidden subgraphs
• On distance-3 matchings and induced matchings
• On independent vertex sets in subclasses of apple-free graphs

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)