Spanning Trees of Bounded Degree Graphs
Abstract
Description
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 $β_d$ such that all connected graphs with degree bounded by $d$ have at least $β_d^μ$ spanning trees where $μ$ is the cyclomatic number or excess of the graph, namely $m-n+1$. We conjecture that $β_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 $β_d$ for $d\le 11$.