DIMACS TR: 2004-34

On Hamiltonicity Of Claw- And Net-Free Graphs



Author: Alexander Kelmans

ABSTRACT
The results of this paper include necessary and sufficient conditions for a claw- and net-free graph $G$ with $s,t \in V(G)$ and $e \in E(G)$ to have $(a1)$ a Hamiltonian path and Hamiltonian $s$--path, $(a2)$ a Hamiltonian $st$--path and Hamiltonian $s$- and $st$--paths containing $e$ if $G$ has connectivity one, and $(a3)$ a Hamiltonian cycle containing $e$ if $G$ is 2--connected. For example, we show that {\em if $G$ is a 2--connected claw- and net-free graph and $e = xy \in E(G)$ then $e$ belongs to a Hamiltonian cycle of $G$ if and only if $G - \{x,y\}$ is connected.} These results imply that a connected claw- and net-free graph has a Hamiltonian path and a 2--connected claw- and 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], and are used in [A. Kelmans, On the Claw- and Net-Free Graphs, a manuscript (1999)] to obtain more general Hamiltonicity results for $k$--connected graphs. Our proofs of $(a1)-(a3)$ 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) 297--316], and provide polynomial time algorithms for solving the corresponding Hamiltonicity problems.

Keywords: claw, net, graph, Hamiltonian path, Hamiltonian cycle, polynomial time algorithm.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-34.ps.gz


DIMACS Home Page