TY - JOUR

T1 - Counting loopy graphs with given degrees

AU - Greenhill, Catherine

AU - McKay, Brendan D.

PY - 2012/2/15

Y1 - 2012/2/15

N2 - Let d=(d 1,d 2,⋯,d n) be a vector of nonnegative integers. We study the number of symmetric 0-1 matrices whose row sum vector equals d. While previous work has focussed on the case of zero diagonal, we allow diagonal entries to equal 1. Specifically, for D∈{1,2} we define the set G D(d) of all n×n symmetric 0-1 matrices with row sums given by d, where each diagonal entry is multiplied by D when forming the row sum. We obtain asymptotically precise formulae for |G D(d)| in the sparse range (where, roughly, the maximum row sum is o(n 1/2)), and in the dense range (where, roughly, the average row sum is proportional to n and the row sums do not vary greatly). The case D=1 corresponds to enumeration by the usual row sum of matrices. The case D=2 corresponds to enumeration by degree sequence of undirected graphs with loops but no repeated edges, due to the convention that a loop contributes 2 to the degree of its incident vertex. We also analyse the distribution of the trace of a random element of G D(d), and prove that it is well approximated by a binomial distribution in the dense range, and by a Poisson binomial distribution in the sparse range.

AB - Let d=(d 1,d 2,⋯,d n) be a vector of nonnegative integers. We study the number of symmetric 0-1 matrices whose row sum vector equals d. While previous work has focussed on the case of zero diagonal, we allow diagonal entries to equal 1. Specifically, for D∈{1,2} we define the set G D(d) of all n×n symmetric 0-1 matrices with row sums given by d, where each diagonal entry is multiplied by D when forming the row sum. We obtain asymptotically precise formulae for |G D(d)| in the sparse range (where, roughly, the maximum row sum is o(n 1/2)), and in the dense range (where, roughly, the average row sum is proportional to n and the row sums do not vary greatly). The case D=1 corresponds to enumeration by the usual row sum of matrices. The case D=2 corresponds to enumeration by degree sequence of undirected graphs with loops but no repeated edges, due to the convention that a loop contributes 2 to the degree of its incident vertex. We also analyse the distribution of the trace of a random element of G D(d), and prove that it is well approximated by a binomial distribution in the dense range, and by a Poisson binomial distribution in the sparse range.

KW - Asymptotic enumeration

KW - Graph

KW - Loop

KW - Poisson binomial distribution

KW - Random graph

KW - Random matrix

KW - Symmetric 0-1 matrix

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

U2 - 10.1016/j.laa.2011.03.052

DO - 10.1016/j.laa.2011.03.052

M3 - Article

SN - 0024-3795

VL - 436

SP - 901

EP - 926

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 4

ER -