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)]