Let $G$ be a caterpillar graph with $n$ vertices. If we remove all the degree one vertices of $G$, the resulting path graph is known as the spine of $G$.
Let $C_1$ and $C_2$ be two caterpillars of order $n$ and spine length $k$. I want to know, what is the necessary and sufficient condition under which $C_1$ and $C_2$ are isomorphic?
Thank you.
Suppose the graph has diameter $2$ or more, to exclude trivial cases.
Let $P_0, \ldots, P_k$ be the "shortest spine" of a caterpillar $G$, i.e. a spine of $G$ such that $P_0$ and $P_k$ do not have degree $1$ (this can be achieved by shortening a spine at the ends if necessary). Let $a_i$ be the degree of $P_i$ for $i = 0, \ldots, k$.
Then the tuple $(a_0, \ldots, a_k)$ uniquely describes $G$ (well, uniquely up to reversal, since $(a_k, \ldots, a_0)$ describes the same caterpillar but backwards.)
This is because this shortest spine $P_0, \ldots, P_n$ of a caterpillar is uniquely determined in each caterpillar by deleting all degree $1$ vertices.
Thus an isomorphism between caterpillars must identify the shortest spines. This is possible iff the sequences of degrees of the shortest spine vertices match up.