According to this paper, there exists a proof that the square of a tree has Hamiltonian cycles iff it is a caterpillar tree. Wikipedia also states a similar point:
They are the trees whose square is a Hamiltonian graph. That is, in a caterpillar, there exists a cyclic sequence of all the vertices in which each adjacent pair of vertices in the sequence is at distance one or two from each other, and trees that are not caterpillars do not have such a sequence. A cycle of this type may be obtained by drawing the caterpillar on two parallel lines and concatenating the sequence of vertices on one line with the reverse of the sequence on the other line.
Source: Wikipedia
There are 2 points which I wish to ask about:
I don't understand Wikipedia's explanation of obtaining Hamiltonian cycles in the square of a caterpillar tree. What does it mean to "draw the caterpillar on two parallel lines"?
How to count the number of Hamiltonian cycles (from a single source) in the square of a caterpillar tree?
I read somewhere that the answer to this would be: $ 2 \times n_1!\times \cdots \times n_k!$, where $n_1, \ldots, n_k $ are the number of leaves attached to each node on the path defining the caterpillar tree. The only exception is a star, when the answer is simply $(n - 1)!$ However, I am unable to understand how these expressions were derived.
Could someone please advise me?
I think the parallel line construction is like this:
That is, the central path alternates between the two lines, and then the leaves from each vertex are on the opposite line.
Then the formula comes from the fact that you can rearrange each set of leaves in any order to get a different cycle, and the factor of $2$ is presumably because you could go in either direction, giving two different cycles for each ordering. In the star there is no extra factor of $2$, because going in the opposite direction is the same as just reversing the order of the leaves.