License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-17997
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1799/
Go to the corresponding Portal


Robson, John Michael

Spanning Trees of Bounded Degree Graphs

pdf-format:
Document 1.pdf (123 KB)


Abstract

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 $dle 11$. First we establish lower bounds on the factor by which the number of spanning trees is multiplied when one new vertex is added to an existing graph so that the new vertex has degree $c$ and the maximum degree of the resulting graph is at most $d$. In all the cases analysed, this lower bound $f_{c,d}$ is attained when the graph before the addition was a complete graph of order $d$ but we have not proved this in general. Next we show that, for any cut of size $c$ cutting a graph $G$ of degree bounded by $d$ into two connected components $G_1$ and $G_2$, the number of spanning trees of $G$ is at least the product of this number for $G_1$ and $G_2$ multiplied by the same factor $f_{c,d}$. Finally we examine the process of repeatedly cutting a graph until no edges remain. The number of spanning trees is at least the product of the multipliers associated with all the cuts. Some obvious constraints on the number of cuts of each size give linear constraints on the normalised numbers of cuts of each size which are then used to lower bound $beta_d$ by the solution of a linear program. The lower bound obtained is significantly improved by imposing a rule that, at each stage, a cut of the minimum available size is chosen and adding some new constraints implied by this rule.

BibTeX - Entry

@InProceedings{robson:DSP:2008:1799,
  author =	{John Michael Robson},
  title =	{Spanning Trees of Bounded Degree Graphs},
  booktitle =	{Moderately Exponential Time Algorithms},
  year =	{2008},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  number =	{08431},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1799},
  annote =	{Keywords: Spanning trees, memorisation, cyclomatic number, bounded degree graphs, cut, linear program.}
}

Keywords: Spanning trees, memorisation, cyclomatic number, bounded degree graphs, cut, linear program.
Seminar: 08431 - Moderately Exponential Time Algorithms
Issue Date: 2008
Date of publication: 23.12.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI