Bounds of a number of leaves of spanning trees

Details Bounds of a number of leaves of spanning trees Bounds of a number of leaves of spanning trees

2011-11-14

arxiv.org/abs/1111.3266v1

Mathematics

Combinatorics

in Russian: PDMI preprint 2/2011. in English not published 15 pages, 6 figures

Scientific paper

We prove that every connected graph with $s$ vertices of degree not 2 has a spanning tree with at least ${1\over 4}(s-2)+2$ leaves. Let $G$ be a be a connected graph of girth $g$ with $v>1$ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge 1$. We prove that $G$ has a spanning tree with at least $\alpha_{g,k}(v(G)-k-2)+2$ leaves, where $\alpha_{g,k}= {[{g+1\over2}]\over [{g+1\over2}](k+3)+1}$ for $k

Affiliated with

Also associated with

No associations

Rating

Bounds of a number of leaves of spanning trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds of a number of leaves of spanning trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds of a number of leaves of spanning trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218815