TOPICS
Search

Centipede Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Centipede

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.

ngraph
1path graph P_2
2path graph P_4
3E graph

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.Seoud, M. Z. and Youssef, M. A. "On Gracefulness of Disconnected Graphs." Unpublished work. Jan. 2017. http://dx.doi.org/10.13140/RG.2.2.17752.49920.

Cite this as:

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

Subject classifications