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).
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.
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.
A40, 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 Sequences3, No. 00.1.1, 2000. http://www.math.uwaterloo.ca/JIS/VOL3/SULANKE/sulanke.
are surrounded by at most two nodes of degree two or greater.
nodes is
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.
, 8, ... as 1, 3, 11, 34, 99, ... (OEIS A052471).
The noncaterpillar trees on 
nodes are illustrated above.
