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