The average number of spanning trees in sparse graphs with given degrees. (June 2017)

• Record Type: Journal Article
• Authors: Greenhill, Catherine; Isaev, Mikhail; Kwan, Matthew; McKay, Brendan D.
• Is Part Of: European journal of combinatorics. Volume 63(2017)
• Page Start: 6
• Page End: 25
• Publication Date: 2017-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.02.003
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence d = ( d 1, …, d n ), provided that the number of edges is at least n + 1 2 d max 4, where d max 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.