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)

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