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 22 references indexed in Scilit:
- Asymptotic enumeration of non-crossing partitions on surfacesDiscrete Mathematics, 2013
- Enumerating simplicial decompositions of surfaces with boundariesEuropean Journal of Combinatorics, 2012
- 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
- Enumeration and limit laws for series–parallel graphsEuropean Journal of Combinatorics, 2007
- Random cubic planar graphsRandom Structures & Algorithms, 2006
- Counting labelled three-connected and homeomorphically irreducible two-connected graphsJournal of Combinatorial Theory, Series B, 1982
- 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