The number of graphs and a random graph with a given degree sequence. Issue 3 (29th February 2012) - Barvinok, Alexander; Hartigan, J.A.
Abstract We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d1, …, dn). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0‐1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013