Random dense bipartite graphs and directed graphs with specified degrees

DOI10.1002/rsa.20273zbMath1208.05066arXivmath/0701600OpenAlexW3083401218MaRDI QIDQ3055774

Brendan D. McKay, Catherine Greenhill

Publication date: 9 November 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0701600

zbMATH Keywords

bipartite graphdigraphdirected graphasymptotic enumerationrandom graph0-1 matrix

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Directed graphs (digraphs), tournaments (05C20) Density (toughness, etc.) (05C42)

Related Items

Factorisation of the complete bipartite graph into spanning semiregular factors, Asymptotic enumeration of digraphs and bipartite graphs by degree sequence, Induced subgraphs in sparse random graphs with given degree sequences, The switch Markov chain for sampling irregular graphs and digraphs, Subgraphs of Dense Random Graphs with Specified Degrees, On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries, The number of graphs and a random graph with a given degree sequence, Random dense bipartite graphs and directed graphs with specified degrees, Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications, Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence, Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

Cites Work

• The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
• The number of matchings in random regular graphs and bipartite graphs
• The asymptotic number of non-negative integer matrices with given row and column sums
• Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of tournaments with a given score sequence
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Random dense bipartite graphs and directed graphs with specified degrees
• Asymptotic Enumeration of Eulerian Circuits in the Complete Graph
• Hamilton Cycles in Random Regular Digraphs
• Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph
• Unnamed Item
• Unnamed Item
• Unnamed Item