TOPICS
Search

Maximum Leaf Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The maximum leaf number l(G) of a graph G is the largest number of tree leaves in any of its spanning trees. (The corresponding smallest number of leaves is known as the minimum leaf number.)

The maximum leaf number and connected domination number d(G) of a graph G are connected by

d(G)+l(G)=|G|,

where n=|G|>2 is the vertex count of G.

Many families of graphs have simple closed forms, as summarized in the following table. In the table, |_x_| denotes the floor function.

graph familymaximum leaf number
Andrásfai graph3n-4
antiprism graphn+1
Apollonian network{3 for n=1; 6 for n=2; 1/2(3^n+5) otherwise
barbell graph2(n-1)
black bishop graph BB_(n,n){1 for n=1; 1/4[2(n-2)n-(-1)^n+9] otherwise
book graph S_(n+1) square P_22n
cocktail party graph K_(n×2)2(n-1)
complete bipartite graph K_(m,n){2 for m=n=1; m+n-1 for min(m,n)=1; m+n-2 otherwise
complete bipartite graph K_(n,n)2(n-1)
complete graph K_nn-1
complete tripartite graph K_(k,m,n){k+m+n-1 for min(k,m,n)=1; k+m+n-2 otherwise
complete tripartite graph K_(n,n,n)3n-2
2n-crossed prism graph2n
crown graph K_2 square K_n^_2(n-2)
cycle graph C_n2
gear graph|_3n/2_|
helm graphn+1
ladder graph nP_2n
Möbius ladder M_nn+1
pan graph3
path graph P_n2
prism graph Y_nn
rook complement graph K_n square K_n^_{1 for n=1; undefined for n=2; n^2-3 otherwise
rook graph K_n square K_nn(n-1)
star graph S_nn-1
sun graph1/4(6n+(-1)^n-1)
sunlet graph C_n circledot K_1n
triangular graph1/2(n^2-3n+4)
web graph2n
wheel graph W_nn-1
white bishop graph WB_(n,n){2 for n=2,3; 1/4[2(n-2)n+(-1)^n+7] otherwise

See also

Connected Dominating Set, Connected Domination Number, Minimum Leaf Number, Spanning Tree, Tree Leaf

Explore with Wolfram|Alpha

References

Fellows, M.; Lokshtanov, D.; Misra, N.; Mnich, M.; Rosamond, F.; and Saurabh, S. "The Complexity Ecology of Parameters: an Illustration Using Bounded Max Leaf Number." Th. Comput. Sys. 45, 822-848, 2009.Lu, H.-I. and Ravi, R. "Approximating Maximum Leaf Spanning Trees in Almost Linear Time." J. Algorithms 29, 132-141, 1998.Solis-Oba, R. "2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves." In Proceedings of Algorithms--ESA '98. 6th Annual European Symposium Venice, Italy, August 24-26, 1998 (Ed. G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci). Belin: Springer, pp. 441-452, 1998.Zhou, G.; Gen, M.; and Wu, T. "A New Approach to the Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm." In IEEE International Conference on Systems, Man, and Cybernetics, 1996, Vol. 4, pp. 2683-2688, 1996.

Cite this as:

Weisstein, Eric W. "Maximum Leaf Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MaximumLeafNumber.html

Subject classifications