Asymptotic enumeration of sparse multigraphs with given degrees
From MaRDI portal
Abstract: Let J and J* be subsets of Z+ such that 0,1in J and 0in 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.
Recommendations
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Counting loopy graphs with given degrees
- Asymptotic enumeration of labeled multigraphs by vertices, edges, and degree parities
- Asymptotic enumeration of sparse uniform hypergraphs with given degrees
- Asymptotic enumeration of sparse graphs with a minimum degree constraint
Cited in
(12)- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- An algebraic approach to electron interactions in quantum Hall systems
- Threshold functions for small subgraphs in simple graphs and multigraphs
- Asymptotic enumeration of linear hypergraphs with given number of vertices and edges
- An algebraic approach to FQHE variational wave functions
- Asymptotic enumeration of sparse 2-connected graphs
- Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
- Asymptotic enumeration of labeled multigraphs by vertices, edges, and degree parities
- Uniform generation of random regular graphs
- Asymptotic enumeration of sparse uniform hypergraphs with given degrees
- The degree-restricted random process is far from uniform
- External columns and chambers of vector partition functions
This page was built for publication: Asymptotic enumeration of sparse multigraphs with given degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408610)
