TY - JOUR

T1 - Asymptotic enumeration of sparse multigraphs with given degrees

AU - Greenhill, Catherine

AU - Mckay, Brendan D.

PY - 2013

Y1 - 2013

N2 - Let J and J be subsets of N such that 0, 1 J and 0 J. For infinitely many n, let k = (k1, . . . , kn) be a vector of nonnegative integers whose sum M is even. We find an asymptotic expression for the number of multigraphs on the vertex set {1, . . . ,n} with degree sequence given by k such that every loop has multiplicity in J and every nonloop edge has multiplicity in J. Equivalently, these are symmetric integer matrices with values J allowed on the diagonal and J off the diagonal. Our expression holds when the maximum degree kmax satisfies kmax = o(M1/3). We prove this result using the switching method, building on an asymptotic enumeration of simple graphs with given degrees [B. D. McKay and N. C. Wormald, Combinatorica, 11 (1991), pp. 369-382]. Our application of the switching method introduces a novel way of combining several different switching operations into a single computation.

AB - Let J and J be subsets of N such that 0, 1 J and 0 J. For infinitely many n, let k = (k1, . . . , kn) be a vector of nonnegative integers whose sum M is even. We find an asymptotic expression for the number of multigraphs on the vertex set {1, . . . ,n} with degree sequence given by k such that every loop has multiplicity in J and every nonloop edge has multiplicity in J. Equivalently, these are symmetric integer matrices with values J allowed on the diagonal and J off the diagonal. Our expression holds when the maximum degree kmax satisfies kmax = o(M1/3). We prove this result using the switching method, building on an asymptotic enumeration of simple graphs with given degrees [B. D. McKay and N. C. Wormald, Combinatorica, 11 (1991), pp. 369-382]. Our application of the switching method introduces a novel way of combining several different switching operations into a single computation.

KW - Asymptotic enumeration

KW - Integer matrix

KW - Multigraph

KW - Switching

KW - Symmetric matrix

UR - http://www.scopus.com/inward/record.url?scp=84891314799&partnerID=8YFLogxK

U2 - 10.1137/130913419

DO - 10.1137/130913419

M3 - Article

SN - 0895-4801

VL - 27

SP - 2064

EP - 2089

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -