Spanning trees in random series-parallel graphs

作者：Ehrenmueller Julia; Rue Juanjo^*

来源：Advances in Applied Mathematics, 2016, 75: 18-55.

DOI：10.1016/j.aam.2015.12.001

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 rho(-n) (1 + o(1)),
where s and rho are computable constants, the values of which are approximately s approximate to 0.09063 and rho(-1) approximate to 2.08415. We obtain analogous results for subfamilies of series-parallel graphs including 2-connected series-parallel graphs, 2-trees, and series-parallel graphs with fixed excess.

• 出版日期2016-4