## DIMACS TR: 2004-35

##
On Claw- And Net-Free Graphs

### Author: Alexander Kelmans

**
ABSTRACT
**
In this paper we describe some structural properties of claw- and
net-free graphs. Using these properties, we find (among other results)
necessary and sufficient conditions for a claw- and net-free graph $G$ with
$s, t \in V(G)$, $s \ne t$, $e \in E(G)$, and disjoint paths $S$ and
$T$ in $G$ to have:
$(c1)$ a Hamiltonian $st$-path,

$(c2)$ a Hamiltonian $s$-path containing $e$,

$(c3)$ a Hamiltonian $st$-path containing $e$
if $G$ is 3-connected,

$(c4)$ a Hamiltonian cycle containing $S$
if $G$ is $k$-connected, $k \ge 2$, and $v(S) \le k$,

$(c5)$ a Hamiltonian path containing $e$ and $S$
if $G$ is $(k+1)$-connected, $k \ge 2$, and $v(S) \le k$,

$(c6)$ a Hamiltonian $st$-path containing $S$ and $T$
if $G$ is $k$-connected, $k \ge 3$, $v(S) + v(T) \le k$, and
$s$, $t$ are end-vertices of paths $S$ and $T$, respectively.

From the above mentioned results we obtain, in particular:

Let $G$ be a claw- and net-free graph. If $G$ is 4-connected,
then for any two different vertices $s$, $t$ and
any edge $e$ in $G$ there is a Hamiltonian
$st$-path in $G$ containing $e$ and, in particular,
every two edges in $G$ belong to a Hamiltonian cycle.
If $G$ is 3-connected then every two non-adjacent edges in $G$ belong
to a Hamiltonian cycle.

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

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

DIMACS Home Page