language-icon Old Web
English
Sign In

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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    5
    References
    5
    Citations
    NaN
    KQI
    []