Consider the caterpillar in part (i) of Fig. 12.50. If we label each edge of the spine with a 1 and each of the other edges with a 0, the caterpillar can be represented by a binary string. Here that binary string is 10001001 where the first 1 is for the first (left-most) edge of the spine, the next three 0's are for the (nonspine) edges at v2, the second 1 is for edge {v2, v3}, the two 0's are for the (nonspine) leaves at v3, and the final 1 accounts for the third (right-most) edge of the spine.
We also note that the reversal of the binary string 10001001-namely, 10010001-corresponds with a second caterpillar that is isomorphic to the one in part (i) of Fig. 12.50.

(a) Find the binary strings for each of the caterpillars in part (ii) of Figs. 12.50 and 12.51.
(b) Can a caterpillar have a binary string of all l's?
(c) Can the binary string for a caterpillar have only two l's?
(d) Draw all the nonisomorphic caterpillars on five vertices. For each caterpillar determine its binary string. How many of these binary strings are palindromes?
(e) Answer the question posed in part (d) upon replacing "five" by "six."
(f) For n ‰¥ 3, prove that the number of nonisomorphic caterpillars on n vertices is (1/2)(2n-3 + 2Œˆ(n-3)/2Œ‹) = 2n-4 + 2ŒŠ(n-4/2Œ‹= 2n-4 + 2ŒŠn/2Œ‹-2. (This was first established in 1973 by F. Harary and A. J. Schwenk.)

Transcribed Image Text:

Spine , V2, vs, va W1 W3 W2 (ii) Spine: w 1 ' w/2, w's, Wa, ws 8 7