2006/07/10 by Alexander Kelmans, Kelmans, Alexander
Computer Science · Mathematics · #05C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C10
paper · pdf · doi:10.48550/arxiv.math/0607234
9 pages
arxiv created 2006/07/10 · openalex publication_date 2006/07/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.