Spanning trees in random series-parallel graphs

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.

References in corpus (2)

• Spanning forests in regular planar maps
• Random planar maps and graphs with minimum degree two and three