ASYMPTOTIC ENUMERATION OF SPARSE MULTIGRAPHS WITH GIVEN DEGREES

作者：Greenhill Catherine^*; McKay Brendan D

来源：SIAM Journal on Discrete Mathematics, 2013, 27(4): 2064-2089.

DOI：10.1137/130913419

• multigraph
• integer matrix
• symmetric matrix
• asymptotic enumeration
• switching

Let J and J* be subsets of N such that 0, 1 is an element of J and 0 is an element of J*. For infinitely many n, let k = (k(1), ... , k(n)) 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 k(max) satisfies k(max) = o(M-1/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.

• 出版日期2013