The number of graphs and a random graph with a given degree sequence. Issue 3 (29th February 2012)

• Record Type: Journal Article
• Authors: Barvinok, Alexander; Hartigan, J.A.
• Is Part Of: Random structures & algorithms. Volume 42:Issue 3(2013)
• Page Start: 301
• Page End: 348
• Publication Date: 2012-02-29
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20409
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We consider the set of all graphs on <italic>n</italic> labeled vertices with prescribed degrees <italic>D</italic> = (<italic>d</italic>₁, …, <italic>d</italic>_{<italic>n</italic>}). For a wide class of <italic>tame</italic> degree sequences <italic>D</italic> we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as <italic>n</italic> grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence <italic>D</italic> is well described by a certain <italic>maximum entropy matrix</italic> computed from <italic>D</italic>. 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</p> </abstract>