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 family maximum leaf number

Andrásfai graph 3n-4

antiprism graph n+1

Apollonian network [画像:{3 for n=1; 6 for n=2; 1/2(3^n+5) otherwise]

barbell graph 2(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_2 2n

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_n n-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 graph 2n

crown graph K_2 square K_n^_ 2(n-2)

cycle graph C_n 2

gear graph |_3n/2_|

helm graph n+1

ladder graph nP_2 n

Möbius ladder M_n n+1

pan graph 3

path graph P_n 2

prism graph Y_n n

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_n n(n-1)

star graph S_n n-1

sun graph 1/4(6n+(-1)^n-1)

sunlet graph C_n circledot K_1 n

triangular graph 1/2(n^2-3n+4)

web graph 2n

wheel graph W_n n-1

white bishop graph WB_(n,n) [画像:{2 for n=2,3; 1/4[2(n-2)n+(-1)^n+7] otherwise]

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

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.

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

Maximum Leaf Number

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications