Let $G = (V,E)$ be a tree, then $G$ is a caterpillar graph $\iff$ The line graph of $G$ contains a Hamiltonian path.

combinatoricsgraph theoryhamiltonian-path

Here the line graph $L(G)$ of $G$ is defined by $L(G) := (E,\{ef : e,f \in E, e \bigcap f \neq \oslash\})$.

I think I have an argument for the forward direction. If G is a caterpillar graph on $n$ vertices then it is a tree where all vertices are within distance 1 of a central path. So if this path has length $k$ we construct a new path of length $k-1$ in $L(G)$.

Label the edges in the simple path $e_1, e_2, …, e_k$ in $G$ in order of connectedness and label the vertices in the simple path just constructed $v_1, v_2, …, v_k$ respectively. Then, on each pair of vertices $(v_i,v_{i+1}), i = 1, 2, …, k-1$, construct the complete graph $K_{r}$ using both $v_i$ and $v_{i+1}$ and $r-2$ new vertices, where $r$ is the number of edges incident on the vertex in $G$ shared by $e_i$ and $e_{i+1}$. Since every complete graph contains a Hamiltonian path between any two vertices, this line graph can be traversed by following such a path in the complete graph from $v_i$ to $v_{i+1}$ when available, and otherwise going straight from $v_i$ to $v_{i+1}$. Have I missed anything?

I am struggling to come up with ideas for the converse.

Best Answer

SKETCH: If $G$ is a tree w a Hamiltonian path then $G$ is a caterpillar graph.

Let $v$ be a vertex of distance 1 from the maximum-length path $P$ in $G$, and let us assume that $v$ has a $S$ set of descendants (all of $v$'s neighbors that are not on the central path). Next, let $u$ be $v$'s neighbour on the central path. Then as $G$ is a tree, there is exactly one such $u$, and moreover in the line graph of $G$, the vertex $z_{uv}$ is a cut vertex; indeed removing $z_{uv}$ cuts the vertices $Z_S =\{z_{ab}; a,b \in S \cup \{v\}\}$ from the rest of the graph. So $\{z_{uv} \}+ Z_S$ must be contiguous vertices on one end of the Hamiltonian path.

This implies that (a) the line graph of $G'=G \setminus [S+\{v\}]$ has a Hamiltonian path $H'$ that ends at an edge incident to $u$. However, (b) each edge $e$ incident to $u$ in $G'$ is a cut edge with each component of $G \setminus \{e\}$ has at least one edge. [Indeed, suffices to show that $u$ is not an endpoint of the path $P$ and neither is any neighbor of $u$ in $P$. However, this is so lest $P$ is not maximum-length after all, otherwise let $u'$ be $u$'s neighbour in $P$ that is an endpoint, then let $P'= P -\{uu'\}+\{uv\}$ $+\{vv'\}$ where $v'$ is a neighbour of $v$ of distance 2 from $P$.] As (a) and (b) contradict each other, there is no Hamiltonian path in $G$ after all.


For the forward direction, basically looks good, but you do need to note that $K_i$ and $K_{i+1}$ intersect at exactly one vertex, lest the Hamiltonian paths in $K_i$ and $K_{i+1}$ intersect besides at the endpoints....i.e., the paths in each of the cliques have to intersect at precisely the endpoints [and no more] and cover all the vertices

Related Question