TOPICS
Search

Spider Graph


Spider

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 n=1, 2, ... nodes are 0, 0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, ... (OEIS A004250).

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

 s_n=P(n-1)-|_(n+1)/2_|,
(1)

where P(n) is the partition function P and |_z_| is the floor function. A generating function for s_n is given by

G(q)=sum_(k=0)^(infty)s_kx^k
(2)
=sum_(n=0)^(infty)(q^(n+4))/((q;q)_(n+3))
(3)
=q^4+2q^5+4q^6+7q^7+11q^8+17q^9+...,
(4)

where (q;a)_n is a q-Pochhammer symbol.

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


See also

Lobster Graph, Tree

Explore with Wolfram|Alpha

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

Subject classifications