Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4

Details Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4 Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4

2012-02-14

arxiv.org/abs/1202.3082v1

Mathematics

Combinatorics

33 pages, 15 figures

Scientific paper

We prove, that every connected graph with $s$ vertices of degree 3 and $t$ vertices of degree at least~4 has a spanning tree with at least ${2\over 5}t +{1\over 5}s+\alpha$ leaves, where $\alpha \ge {8\over 5}$. Moreover, $\alpha \ge 2$ for all graphs besides three exclusions. All exclusion are regular graphs of degree~4, they are explicitly described in the paper. We present infinite series of graphs, containing only vertices of degrees~3 and~4, for which the maximal number of leaves in a spanning tree is equal for ${2\over 5}t +{1\over 5}s+2$. Therefore we prove that our bound is tight.

Affiliated with

Also associated with

No associations

Rating

Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4 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 Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-90032