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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.