The number of caterpillars

Harary, Frank; Schwenk, Allen J.

1973

Citation: Harary, Frank, Schwenk, Allen J. (1973)."The number of caterpillars." Discrete Mathematics 6(4): 359-365. <http://hdl.handle.net/2027.42/33977>

Abstract: A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed. The number of nonisomorphic caterpillars with n+4 points is 2n + 2[n/2]. This neat formula is proved in two ways: first, as a special case of an application of Polya's enumeration theorem which counts graphs with integer-weighted points; secondly, by an appropriate labeling of the lines of the caterpillar.

DOIs: http://dx.doi.org/10.1016/0012-365X(73)90067-8

URI: http://www.sciencedirect.com/science/article/B6V00-48FM0KJ-1M/2/431c511acd2f4a13316bbcf9c68810dc

Handle: http://hdl.handle.net/2027.42/33977

Show full item record