Steklov Institute of Mathematics at St.Petersburg

PREPRINT 04/2007


H..

This preprint was accepted March 9, 2007

ABSTRACT:
We prove the following theorem: every connected graph with $k$
vertices of degree at least 4 and $m$ vertices of degree
3 has a spanning tree  with at least $\lceil\frac{2}{5} \cdot k + \frac{2}{15} \cdot m\rceil$
leaves.
[Full text: (.ps.gz)]
Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg