Mathematics – Combinatorics
Scientific paper
2006-07-10
Mathematics
Combinatorics
9 pages
Scientific paper
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.
Kelmans Alexander
No associations
LandOfFree
On Hamiltonicity of {claw, net}-free graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Hamiltonicity of {claw, net}-free graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Hamiltonicity of {claw, net}-free graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-152348