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

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}{claw,net}-free graph G   with s,t∈V(G)s,t∈V(G) and e∈E(G)e∈E(G) to have (1) a Hamiltonian s-path, (2) a Hamiltonian st-path, (3) a Hamiltonian s- and st-paths containing 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}{claw,net}-free graph has a Hamiltonian path and a 2-connected {claw,net}{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, pp. 297–316]. Our proofs of (1)–(4) are shorter than the proofs of their corollaries in [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, pp. 297–316], and provide polynomial-time algorithms for solving the corresponding Hamiltonicity problems.