Spanning trees in random series-parallel graphs

Original · EN

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 ⁻ⁿ (1+o(1)), where s and are computable constants, the values of which are approximately s ≈ 0.09063 and ⁻¹ ≈ 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.