Spanning Trees of Bounded Degree Graphs

Details Spanning Trees of Bounded Degree Graphs Spanning Trees of Bounded Degree Graphs

2009-02-12

arxiv.org/abs/0902.2166v1

Computer Science

Discrete Mathematics

Scientific paper

We consider lower bounds on the number of spanning trees of connected graphs with degree bounded by $d$. The question is of interest because such bounds may improve the analysis of the improvement produced by memorisation in the runtime of exponential algorithms. The value of interest is the constant $\beta_d$ such that all connected graphs with degree bounded by $d$ have at least $\beta_d^\mu$ spanning trees where $\mu$ is the cyclomatic number or excess of the graph, namely $m-n+1$. We conjecture that $\beta_d$ is achieved by the complete graph $K_{d+1}$ but we have not proved this for any $d$ greater than 3. We give weaker lower bounds on $\beta_d$ for $d\le 11$.

Affiliated with

Also associated with

No associations

Rating

Spanning Trees of Bounded Degree Graphs 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 of Bounded Degree Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning Trees of Bounded Degree Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556841