###
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