Research Library

Premium The number of graphs and a random graph with a given degree sequence
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)
SCImago Journal Rank1.314

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here