TOPICS

Centipede Graph


Centipede

The n-centipede graph, n-centipede tree, or simply "n-centipede," is the tree on 2n nodes obtained by joining the bottoms of n copies of the path graph P_2 laid in a row with edges. It is therefore isomorphic to the (n,2)-firecracker graph, with special cases summarized in the table below.

The rank polynomial of the n-centipede is given by

 R_n(x,y)=(x+1)^(2n-1).

See also

Caterpillar Graph, Firecracker Graph, Ladder Graph, Ladder Rung Graph, Tree

Explore with Wolfram|Alpha

References

Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 (Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.

Cite this as:

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

Subject classifications