z-logo
Premium
The number of graphs and a random graph with a given degree sequence
Author(s) -
Barvinok Alexander,
Hartigan J.A.
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20409
Subject(s) - mathematics , combinatorics , bipartite graph , degree (music) , corollary , discrete mathematics , random regular graph , random graph , sequence (biology) , indifference graph , graph , chordal graph , 1 planar graph , physics , biology , acoustics , genetics
Abstract We consider the set of all graphs on n labeled vertices with prescribed degrees D = ( d 1 ,…, d n ). 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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here