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