Petersburg Department of Steklov Institute of Mathematics

PREPRINT 05/2001


. .

This preprint was accepted June, 2001
Contact: . .

ABSTRACT:
We prove that for every connected graph~$G(V,E)$ with minimal vertex
degree~$d$ (where~$3\leq d\leq 5$) there exists a spanning tree with more
than~$|V|\cdot{d-2\over d+1}$ end vertices. We construct series of
examoles of extremal graphs and show that the constant~${d-2\over d+1}$
cannot be replaced by bigger one.

We prove that for every connected graph~$G(V,E)$ with minimal vertex
degree~$d$ (where~$d\geq  6$) there exists a spanning tree with more
than~$|V|\cdot{ \sqrt{d}-1\over \sqrt{d}+1}$ end vertices.


                       
[ Full text: (.ps.gz)]
Back to all preprints
Back to the Petersburg Department of Steklov Institute of Mathematics