Caterpillar Graph

A caterpillar graph, caterpillar tree, or simply "caterpillar," is a tree in which every graph vertex is on a central stalk or only one graph edge away from the stalk (in other words, removal of its endpoints leaves a path graph; Gallian 2007). A tree is a caterpillar iff all nodes of degree  are surrounded by at most two nodes of degree two or greater.

An n-alkane graph is also sometimes known as a caterpillar graph (Boesch et al. 1974; Merrifield and Simmons 1989, pp. 161-162).

Caterpillar graphs are graceful.

The number of caterpillar trees on  nodes is

where  is the floor function (Harary and Schwenk 1973). For , 2, ... nodes, this gives 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, ... (OEIS A005418). The first few caterpillars are illustrated above.

The number of noncaterpillar trees on , 8, ... as 1, 3, 11, 34, 99, ... (OEIS A052471). The noncaterpillar trees on  nodes are illustrated above.

REFERENCES

Boesch, F. T.; Chen, S.; and McHugh, J. A. M. "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.

Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.

Gardner, M. Wheels, Life, and other Mathematical Amusements. New York: W. H. Freeman, p. 160, 1983.

Gutman, I. and El-Basil, S. "Topological Properties of Benzenoid Systems. XXXVII. Characterization of Certain Chemical Graphs." Z. Naturforsch. A 40, 923-926, 1985.

Harary, F. and Schwenk, A. J. "The Number of Caterpillars." Disc. Math. 6, 359-365, 1973.

Hoffman, N. "Binary Grids and a Related Counting Problem." Two Year Coll. Math. J. 9, 267-272, 1978.

Horton, M. "Graceful Trees: Statistics and Algorithms." Bachelor of Computing with Honours thesis. University of Tasmania, 2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.

Merrifield, R. E. and Simmons, H. E. Topological Methods in Chemistry. New York: Wiley, 1989.

Sloane, N. J. A. Sequences A005418/M0771 and A052471 in "The On-Line Encyclopedia of Integer Sequences."Sulanke, R. A. "Moments of Generalized Motzkin Paths." J. Integer Sequences 3, No. 00.1.1, 2000. http://www.math.uwaterloo.ca/JIS/VOL3/SULANKE/sulanke.