Spanning trees with many leaves
2011
Let a maximal chain of vertices of degree 2 in a graph G consist of k > 0 vertices. We prove that G has a spanning tree with more than $$ \frac{{v(G)}}{{2k + 4}} $$
leaves (where υ(G) is the number of vertices of the graph G). We present an infinite series of examples showing that the constant $$ \frac{1}{{2k + 4}} $$
cannot be enlarged. Bibliography: 7 titles.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
5
References
5
Citations
NaN
KQI