TOPICS
Search

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 >=3 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.

CaterpillarTrees

The number of caterpillar trees on n>=3 nodes is

 C_n=2^(n-4)+2^(|_n/2-2_|),

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

CaterpillarGraph

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


See also

Banana Tree, Centipede Graph, Lobster Graph, Tree

Explore with Wolfram|Alpha

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.

Cite this as:

Weisstein, Eric W. "Caterpillar Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CaterpillarGraph.html

Subject classifications