TOPICS

Spider Graph

A spider graph, spider tree, or simply "spider," is a tree with one vertex of degree at least 3 and all others with degree at most 2. The numbers of spiders on , 2, ... nodes are 0, 0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, ... (OEIS A004250).

The count of spider trees with nodes is the same as the number of integer partitions of into three or more parts. It also has closed form

 (1)

where is the partition function P and is the floor function. A generating function for is given by

 (2) (3) (4)

where is a q-Pochhammer symbol.

Not all spiders are caterpillar graphs, nor are all spiders lobster graphs.

Lobster Graph, Tree

Explore with Wolfram|Alpha

More things to try:

References

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.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.Sloane, N. J. A. Sequence A004250/M1046 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

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