Asymptotic enumeration of sparse multigraphs with given degrees

Catherine Greenhill, Brendan D. Mckay

    Research output: Contribution to journalArticlepeer-review

    8 Citations (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)2064-2089
    Number of pages26
    JournalSIAM Journal on Discrete Mathematics
    Issue number4
    Publication statusPublished - 2013


    Dive into the research topics of 'Asymptotic enumeration of sparse multigraphs with given degrees'. Together they form a unique fingerprint.

    Cite this