TOPICS
Search

Maximum Leaf Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The maximum leaf number l(G) of a finite connected graph G is the largest number of tree leaves in any of its spanning trees. (The corresponding smallest number of tree 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, and M denotes a perfect matching of K_(n,n).

The parameters in the table are positive integers. In the Apollonian network row, n counts the face-subdivision steps of the deterministic planar construction starting from a triangle (Jin et al. 2017).

graph familymaximum leaf number
Andrásfai graph{2 for n=1; 3n-4 for n>=2
antiprism graphn+1
Apollonian network{3 for n=1; 6 for n=2; 13·3^(n-3) for n>=3
barbell graph{2 for n=1; 2(n-1) for n>=2
black bishop graph BB_(n,n){0 for n=1; 1/4[2(n-2)n-(-1)^n+9] for n>=2
book graph S_(n+1) square P_22n
cocktail party graph K_(n×2){undefined for n=1; 2(n-1) for n>=2
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 for n=1; 2(n-1) for n>=2
complete graph K_n{0 for n=1; 2 for n=2; n-1 for n>=3
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){2 for n=1; 3n-2 for n>=2
2n-crossed prism graph2n
crown graph K_(n,n)-M{undefined for n=1,2; 2(n-2) for n>=3
cycle graph C_n2
gear graph|_3n/2_|
helm graphn+1
ladder graph nP_2{2 for n=1; 4 for n=3; n for n=2 or n>=4
Möbius ladder M_nn+1
pan graph3
path graph P_n{0 for n=1; 2 for n>=2
prism graph Y_n{4 for n=3; n for n>=4
rook complement graph K_n square K_n^_{0 for n=1; undefined for n=2; n^2-3 for n>=3
rook graph K_n square K_nn(n-1)
star graph S_n{0 for n=1; 2 for n=2; n-1 for n>=3
sun graph1/4(6n+(-1)^n-1)
sunlet graph C_n circledot K_1n
triangular graph{0 for n=2; 1/2(n^2-3n+4) for n>=3
web graph2n
wheel graph W_nn-1
white bishop graph WB_(n,n){undefined for n=1; 2 for n=2,3; 1/4[2(n-2)n+(-1)^n+7] for n>=4

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.Jin, Y.; Li, H.; and Zhang, Z. "Maximum Matchings and Minimum Dominating Sets in Apollonian Networks and Extended Tower of Hanoi Graphs." Theor. Comput. Sci. 703, 37-54, 2017. https://doi.org/10.1016/j.tcs.2017.08.024.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). Berlin, Germany: 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.

Referenced on Wolfram|Alpha

Maximum Leaf Number

Cite this as:

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

Subject classifications