TOPICS
Search

Tree Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The term tree number is used in more than one sense in graph theory.

In this entry, the tree number of a graph G refers to the number of its spanning trees (Kook 2011, p. 417). The same quantity is also called the graph complexity or simply the complexity of G (Harary and Palmer 1973, p. 268), and is commonly denoted tau(G) or kappa(G). This graph property is implemented as GraphData[graph, "SpanningTreeCount"].

In another usage, the tree number of a graph G is the minimum number of tree subgraphs whose edge sets partition the edge set of G (Vanetik 2009, p. 1). This edge-partition convention is related to arboricity, but differs from it because arboricity partitions the edge set into forests rather than into individual trees. An edgeless graph has tree number 0 in this convention. The edge-partition convention is implemented as GraphData[graph, "TreeNumber"].

The following table summarizes the tree numbers (i.e., spanning tree counts) of various named classes of graphs. The index of each value list in the table starts at 1. An X indicates that the family in that row is not defined for the corresponding parameter value. The king, knight, queen, rook, and fiveleaper rows use n×n boards, and the fan row uses F_(n,n).

classOEIStree numbers
Andrásfai graphA1931261, 5, 392, 130691, 116268789, 217138318913, ...
antiprism graphA193127X, X, 384, 3528, 30250, 248832, 1989806, ...
Apollonian networkA19312816, 1445, 487350000, 6820689973308563232421875, ...
barbell graphA193129X, X, 9, 256, 15625, 1679616, 282475249, ...
book graph S_(n+1) square P_2A0062344, 15, 54, 189, 648, 2187, 7290, 24057, ...
cocktail party graph K_(n×2)A1931300, 4, 384, 82944, 32768000, 20736000000, ...
complete graph K_nA0002721, 1, 3, 16, 125, 1296, 16807, 262144, ...
complete bipartite graph K_(n,n)A0680871, 4, 81, 4096, 390625, 60466176, 13841287201, ...
complete tripartite graph K_(n,n,n)A1931313, 384, 419904, 1610612736, 15000000000000, ...
crossed prism graphA193132X, X, X, 384, X, 9216, X, 196608, X, 3932160, ...
crown graphA193133X, X, 6, 384, 40500, 6635520, 1575656250, ...
cube-connected cycle graphX, X, 32400000, 5068660643117137920000, ...
cycle graph C_nA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, ...
fan graph F_(n,n)1, 8, 216, 13056, 1409375, ...
fiveleaper graph1, 0, 0, 0, 0, 0, 0, 331898989520947048842445518274560, ...
folded cube graphA193134X, 1, 16, 4096, 2147483648, 14167099448608935641088, ...
gear graphA129743X, X, 50, 192, 722, 2700, 10082, 37632, 140450, 524172
grid graph P_n square P_nA0073411, 4, 192, 100352, 557568000, 32565539635200, ...
grid graph P_n square P_n square P_nA0717631, 384, 8193540096000, ...
halved cube graphA1931351, 1, 16, 82944, 126806761930752, ...
Hanoi graphA1931363, 135, 20503125, 119709242282867431640625, ...
helm graphA004146X, X, 16, 45, 121, 320, 841, 2205, 5776, 15125, ...
hypercube graph Q_nA0062371, 4, 384, 42467328, 20776019874734407680, ...
king graph1, 16, 17745, 1064918960, 3271331573452800, ...
knight graph1, 0, 0, 144000, 136323072000, 5398085382092881920, ...
ladder graph P_2 square P_nA0013531, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, ...
Möbius ladder M_nA020871X, X, 81, 392, 1815, 8112, 35301, 150544, 632043, ...
Mycielski graphA1931481, 1, 5, 38642, 3568248132106250, ...
odd graphA1931491, 3, 2000, 336140000000000000, ...
pan graphA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, ...
path graph P_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
permutation star graphA1931501, 1, 6, 162000000, ...
prism graphA006235X, X, 75, 384, 1805, 8100, 35287, 150528, ...
queen graph1, 16, 541205, 54711160897536, ...
rook graphA1931371, 4, 11664, 34359738368, 156250000000000000000, ...
star graph S_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
sun graphA193152X, X, 54, 600, 9610, 202800, 5329646, 167968080, ...
sunlet graph C_n circledot K_1A000027X, X, 3, 4, 5, 6, 7, 8, 9, 10
tetrahedral Johnson graphX, X, X, X, X, 96745881600000000, ...
triangular graphA193154X, 1, 3, 384, 2048000, 518400000000, ...
web graphA006235X, X, 75, 384, 1805, 8100, 35287, 150528, ...
wheel graph W_nA004146X, X, X, 16, 45, 121, 320, 841, 2205, ...

Closed forms for tree numbers of various named classes of graphs are given in the table below, where phi is the golden ratio, L_n is a Lucas number, U_n(x) is a Chebyshev polynomial of the second kind, and C_n^((m))(x) is a Gegenbauer polynomial. tau(W_n) was considered by Koshy (2001) and Alikhani and Ghanbari (2024, pp. 3-4). In the latter source, the wheel graph parameter counts rim vertices, so its W_n is this work's W_(n+1) on n+1 vertices. The formulas apply where their named graphs are defined: n>=3 for antiprisms, cycles, helms, Möbius ladders, pans, prisms, and sunlets; n>=4 for wheels; and even n>=4 for crossed prisms. The other formulas use positive integer n, with the empty product equal to 1 at singleton graph instances of the grid graph.

classclosed form
antiprism graph2/5n(phi^(4n)+phi^(-4n)-2)
book graph S_(n+1) square P_23^(n-1)(n+3)
cocktail party graph K_(n×2)4^(n-1)(n-1)^nn^(n-2)
complete graph K_nn^(n-2)
complete bipartite graph K_(n,n)n^(2n-2)
complete tripartite graph K_(n,n,n)3·8^(n-1)n^(3n-2)
crossed prism graph3n·2^(2n-3)
cycle graph C_nn
grid graph P_n square P_n(2^(n^2-1))/(n^2)product_(i,j=0; i,j not both 0)^(n-1)[2-cos((pii)/n)-cos((pij)/n)]
grid graph P_n square P_n square P_n(2^(n^3-1))/(n^3)product_(i,j,k=0; i,j,k not all 0)^(n-1)[3-cos((pii)/n)-cos((pij)/n)-cos((pik)/n)]
helm graphL_(2n)-2
hypercube graph Q_n2^(2^n-1-n)product_(k=1)^(n)k^((n; k))
ladder graph P_2 square P_n((2+sqrt(3))^n-(2-sqrt(3))^n)/(2sqrt(3))
=(sinh(ncosh^(-1)2))/(sqrt(3))
=U_(n-1)(2)
=C_(n-1)^((1))(2)
Möbius ladder M_n1/2n[2+(2+sqrt(3))^n+(2-sqrt(3))^n]
pan graphn
path graph P_n1
prism graph Y_n1/2n[(2-sqrt(3))^n+(2+sqrt(3))^n-2]
star graph S_n1
sunlet graph C_n circledot K_1n
wheel graph W_nL_(2(n-1))-2

See also

Matrix Tree Theorem, Spanning Tree

Explore with Wolfram|Alpha

References

Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.Kook, W. "Combinatorial Green's Function of a Graph and Applications to Networks." Adv. Appl. Math. 46, 417-423, 2011.Koshy, T. Fibonacci and Lucas Numbers with Applications. New York: Wiley-Interscience, 2001.Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A000272/M3027, A001353/M3499, A004146/M3867, A006234/M3496, A006235/M4849, A006237/M3725, A007341, A020871, A068087, A071763, A129743, A193126, A193127, A193128, A193129, A193130, A193131, A193132, A193133, A193134, A193135, A193136, A193137, A193148, A193149, A193150, A193151, A193152, A193153, and A193154 in "The On-Line Encyclopedia of Integer Sequences."Vanetik, N. "Computing the Tree Number of a Cut-Outerplanar Graph." 2 Jun 2009. https://arxiv.org/abs/0906.0422v1.

Cite this as:

Weisstein, Eric W. "Tree Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TreeNumber.html

Subject classifications