Options
Spanning trees in random series-parallel graphs
Publikationstyp
Journal Article
Date Issued
2016-04-01
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
75
Start Page
18
End Page
55
Citation
Advances in Applied Mathematics (75): 18-55 (2016-04-01)
Publisher DOI
Scopus ID
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 forms sρ-n(1+o(1)), where s and ρ are computable constants, the values of which are approximately s ≈ 0.09063 and ρ-1 ≈ 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.
Subjects
MSC primary 05A16
secondary 05C10