Analytic combinatorics of connected graphs. Issue 2 (25th January 2019)

• Record Type: Journal Article
• Authors: Panafieu, Élie
• Is Part Of: Random structures & algorithms. Volume 55:Issue 2(2019)
• Page Start: 427
• Page End: 495
• Publication Date: 2019-01-25
• Subjects: analytic combinatorics -- asymptotic expansion -- connected graphs -- generating functions; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20836
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We enumerate the connected graphs that contain a number of edges growing linearly with respect to the number of vertices. So far, only the first term of the asymptotics and a bound on the error were known. Using analytic combinatorics, that is, generating function manipulations, we derive a formula for the coefficients of the complete asymptotic expansion. The same result is derived for connected multigraphs.