The average number of spanning trees in sparse graphs with given degrees

Greenhill C, Isaev M, Kwan MA, McKay BD. 2017. The average number of spanning trees in sparse graphs with given degrees. European Journal of Combinatorics. 63, 6–25.


Journal Article | Published | English

Scopus indexed
Author
Greenhill, Catherine; Isaev, Mikhail; Kwan, Matthew AlanIST Austria; McKay, Brendan D.
Abstract
We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence , provided that the number of edges is at least , where is the maximum degree. A key part of our argument involves establishing a concentration result for a certain family of functions over random trees with given degrees, using Prüfer codes.
Publishing Year
Date Published
2017-06-01
Journal Title
European Journal of Combinatorics
Volume
63
Page
6-25
ISSN
IST-REx-ID

Cite this

Greenhill C, Isaev M, Kwan MA, McKay BD. The average number of spanning trees in sparse graphs with given degrees. European Journal of Combinatorics. 2017;63:6-25. doi:10.1016/j.ejc.2017.02.003
Greenhill, C., Isaev, M., Kwan, M. A., & McKay, B. D. (2017). The average number of spanning trees in sparse graphs with given degrees. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2017.02.003
Greenhill, Catherine, Mikhail Isaev, Matthew Alan Kwan, and Brendan D. McKay. “The Average Number of Spanning Trees in Sparse Graphs with given Degrees.” European Journal of Combinatorics. Elsevier, 2017. https://doi.org/10.1016/j.ejc.2017.02.003.
C. Greenhill, M. Isaev, M. A. Kwan, and B. D. McKay, “The average number of spanning trees in sparse graphs with given degrees,” European Journal of Combinatorics, vol. 63. Elsevier, pp. 6–25, 2017.
Greenhill C, Isaev M, Kwan MA, McKay BD. 2017. The average number of spanning trees in sparse graphs with given degrees. European Journal of Combinatorics. 63, 6–25.
Greenhill, Catherine, et al. “The Average Number of Spanning Trees in Sparse Graphs with given Degrees.” European Journal of Combinatorics, vol. 63, Elsevier, 2017, pp. 6–25, doi:10.1016/j.ejc.2017.02.003.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1606.01586

Search this title in

Google Scholar