pith. sign in

arxiv: 1303.4218 · v2 · pith:VVDAT526new · submitted 2013-03-18 · 🧮 math.CO

Asymptotic enumeration of sparse multigraphs with given degrees

classification 🧮 math.CO
keywords asymptoticgivenswitchingdegreedegreesdiagonalenumerationevery
0
0 comments X
read the original abstract

Let J and J* be subsets of Z+ such that 0,1\in J and 0\in 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 non-loop 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 satisfies K = o(M^(1/3)). We prove this result using the switching method, building on an asymptotic enumeration of simple graphs with given degrees (McKay and Wormald, 1991). Our application of the switching method introduces a novel way of combining several different switching operations into a single computation.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.