Premium
Analytic combinatorics of connected graphs
Author(s) -
Panafieu Élie
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20836
Subject(s) - combinatorics , mathematics , generating function , extremal combinatorics , enumerative combinatorics , discrete mathematics , term (time) , function (biology) , physics , quantum mechanics , evolutionary biology , biology
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.