Spanning trees in random series-parallel graphs
Preprint
Abstract
By means of analytic techniques we show that the expected number of spanning trees in a connected labelled series-parallel graph on $n$ vertices chosen uniformly at random satisfies an estimate of the form $s \varrho^{-n} (1+o(1))$, where $s$ and $\varrho$ are computable constants, the values of which are approximately $s \approx 0.09063$ and $\varrho^{-1} \approx 2.08415$. We obtain analogue results for subfamilies of series-parallel graphs including 2-connected series-parallel graphs, 2-trees, and series-parallel graphs with fixed excess.
Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Graph classes with given 3‐connected components: Asymptotic enumeration and random graphsRandom Structures & Algorithms, 2012
- Vertices of given degree in series‐parallel graphsRandom Structures & Algorithms, 2009
- The structure of unicellular maps, and a connection between maps of positive genus and planar labelled treesProbability Theory and Related Fields, 2009
- A Characterization of the Tutte Polynomial via Combinatorial EmbeddingsAnnals of Combinatorics, 2008
- Random cubic planar graphsRandom Structures & Algorithms, 2006
- On Convergence Rates in the Central Limit Theorems for Combinatorial StructuresEuropean Journal of Combinatorics, 1998
- The number of spanning trees in graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- The number of spanning trees in regular graphsRandom Structures & Algorithms, 1990
- The number of connected sparsely edged graphs. II. Smooth graphs and blocksJournal of Graph Theory, 1978
- The number of connected sparsely edged graphsJournal of Graph Theory, 1977