# zbMATH — the first resource for mathematics

Spanning trees with many leaves. (English) Zbl 0734.05041
It is known that the problem of finding a spanning tree with maximum number of leaves is NP-complete. The paper presents an algorithm constructing a spanning tree with at least $$n/4+2$$ leaves for any connected n-vertex graph degrees of whose nodes are 3 or greater. The algorithm is further extended for the connected graphs with minimum degree at least 4. A spanning tree constructed by this algorithm contains at least $$(2n+8)/5$$ leaves.
These algorithms along with some additional algorithmical approaches give the following upper and lower bounds of the value l(n,k) denoting the maximum integer m such that every connected n-vertex graph with minimum degree at least k has a spanning tree with at least m leaves: $$\quad l(n,3)\geq n/4+2,l(n,4)\geq (2n+8)/5,l(n,k)\leq n-3\quad \lfloor n/(k+1)\rfloor +2,l(n,k)\geq (1-b \ln k/k)n,$$where the last inequality (for $$b>2.5)$$ holds for k sufficiently large.
Reviewer: R.Jirousek (Praha)

##### MSC:
 05C05 Trees 05C35 Extremal problems in graph theory 68R10 Graph theory (including graph drawing) in computer science
spanning tree
Full Text: