Premium The number of graphs and a random graph with a given degree sequencePremium

Author(s)

Barvinok Alexander,

Hartigan J.A.

Publication year2013

Publication title

random structures and algorithms

Resource typeJournals

PublisherWiley Subscription Services

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

Subject(s)1 planar graph , acoustics , biology , bipartite graph , chordal graph , combinatorics , corollary , degree (music) , discrete mathematics , genetics , graph , indifference graph , mathematics , physics , random graph , random regular graph , sequence (biology)

Language(s)English

SCImago Journal Rank1.314

H-Index69

eISSN1098-2418

pISSN1042-9832

DOI10.1002/rsa.20409

Seeing content that should not be on Zendy? Contact us.