Maximum Leaf Number
المؤلف:
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
الجزء والصفحة:
...
22-5-2022
5682
Maximum Leaf Number
The maximum leaf number 
of a graph 
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 
of a graph 
are connected by
where 
is the vertex count of 
.
Many families of graphs have simple closed forms, as summarized in the following table. In the table, 
denotes the floor function.
| graph family |
maximum leaf number |
| Andrásfai graph |
 |
| antiprism graph |
 |
| Apollonian network |
![<span style=]() {3 for n=1; 6 for n=2; 1/2(3^n+5) otherwise" src="https://mathworld.wolfram.com/images/equations/MaximumLeafNumber/Inline10.svg" style="height:108px; width:225px" /> |
| barbell graph |
 |
black bishop graph  |
![<span style=]() {1 for n=1; 1/4[2(n-2)n-(-1)^n+9] otherwise" src="https://mathworld.wolfram.com/images/equations/MaximumLeafNumber/Inline13.svg" style="height:72px; width:401px" /> |
book graph  |
 |
cocktail party graph  |
 |
complete bipartite graph  |
![<span style=]() {2 for m=n=1; m+n-1 for min(m,n)=1; m+n-2 otherwise" src="https://mathworld.wolfram.com/images/equations/MaximumLeafNumber/Inline19.svg" style="height:104px; width:306px" /> |
complete bipartite graph  |
 |
complete graph  |
 |
complete tripartite graph  |
![<span style=]() {k+m+n-1 for min(k,m,n)=1; k+m+n-2 otherwise" src="https://mathworld.wolfram.com/images/equations/MaximumLeafNumber/Inline25.svg" style="height:68px; width:376px" /> |
complete tripartite graph  |
 |
 -crossed prism graph |
 |
crown graph  |
 |
cycle graph  |
2 |
| gear graph |
 |
| helm graph |
 |
ladder graph  |
 |
Möbius ladder  |
 |
| pan graph |
3 |
path graph  |
2 |
prism graph  |
 |
rook complement graph  |
![<span style=]() {1 for n=1; undefined for n=2; n^2-3 otherwise" src="https://mathworld.wolfram.com/images/equations/MaximumLeafNumber/Inline43.svg" style="height:104px; width:230px" /> |
rook graph  |
 |
star graph  |
 |
| sun graph |
 |
sunlet graph  |
 |
| triangular graph |
 |
| web graph |
 |
wheel graph  |
 |
white bishop graph  |
![<span style=]() {2 for n=2,3; 1/4[2(n-2)n+(-1)^n+7] otherwise" src="https://mathworld.wolfram.com/images/equations/MaximumLeafNumber/Inline56.svg" style="height:72px; width:435px" /> |
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
