Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
From MaRDI portal
Publication:6074864
Abstract: We provide asymptotic formulae for the numbers of bipartite graphs with given degree sequence, and of loopless digraphs with given in- and out-degree sequences, for a wide range of parameters. Our results cover medium range densities and close the gaps between the results known for the sparse and dense ranges. In the case of bipartite graphs, these results were proved by Greenhill, McKay and Wang in 2006 and by Canfield, Greenhill and McKay in 2008, respectively. Our method also essentially covers the sparse range, for which much less was known in the case of loopless digraphs. For the range of densities which our results cover, they imply that the degree sequence of a random bipartite graph with m edges is accurately modelled by a sequence of independent binomial random variables, conditional upon the sum of variables in each part being equal to m. A similar model also holds for loopless digraphs.
Recommendations
- Degree sequences of random digraphs and bipartite graphs
- Random dense bipartite graphs and directed graphs with specified degrees
- The number of graphs and a random graph with a given degree sequence
- Asymptotic enumeration of graphs with given degree sequence
- Asymptotic enumeration by degree sequence of graphs of high degree
Cites work
- scientific article; zbMATH DE number 3878944 (Why is no real title available?)
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 3435482 (Why is no real title available?)
- Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
- Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
- Asymptotics and random matrices with row-sum and column sum-restrictions
- Complex martingales and asymptotic enumeration
- Degree sequences of random digraphs and bipartite graphs
- On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
- Random dense bipartite graphs and directed graphs with specified degrees
- Some problems in the enumeration of labelled graphs
- The asymptotic number of integer stochastic matrices
- The asymptotic number of non-negative integer matrices with given row and column sums
- The degree sequence of a random graph. I. The models
- The enumeration of arrays and a generalization related to contingency tables
- The number of graphs and a random graph with a given degree sequence
- The number of matchings in random regular graphs and bipartite graphs
- Transversal theory. An account of some aspects of combinatorial mathematics
Cited in
(11)- scientific article; zbMATH DE number 861357 (Why is no real title available?)
- Random dense bipartite graphs and directed graphs with specified degrees
- Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- The number of graphs and a random graph with a given degree sequence
- Complex martingales and asymptotic enumeration
- scientific article; zbMATH DE number 91021 (Why is no real title available?)
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Degree sequences of random digraphs and bipartite graphs
- Asymptotic enumeration of Cayley digraphs
- Asymptotic enumeration of graphs with given degree sequence
This page was built for publication: Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074864)
