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.

Equivalently, the n-centipede graph is the graph corona product P_n circledot K_1.

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, Graph Corona Product, Ladder Graph, Ladder Rung Graph, Tree

Explore with Wolfram|Alpha

References

House of Graphs. Centipede Graphs. K2, The Path P4, E Graph (T(2,3,2)), Corona of P4, T(2,3,3,3,2), T(2,3,3,3,3,2), Centipede Graph 7, Centipede Graph 8, Centipede Graph 9, and Centipede Graph 10.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. A. and Youssef, M. Z. "On Gracefulness of Disconnected Graphs." Unpublished manuscript. 2017. https://doi.org/10.13140/RG.2.2.17752.49920.

Referenced on Wolfram|Alpha

Centipede Graph

Cite this as:

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

Subject classifications