Centipede Graph


The n-centipede graph, n-centipede tree, n-comb graph (Seoud and Youssef 2017), 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


See also

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

Explore with Wolfram|Alpha


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.Seoud, M. Z. and Youssef, M. A. "On Gracefulness of Disconnected Graphs." Unpublished work. Jan. 2017.

Cite this as:

Weisstein, Eric W. "Centipede Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications