An exact threshold theorem for random graphs and the node-packing problem
From MaRDI portal
The random digraph \(D_ n(m)\) has a uniform probability distribution on the set of digraphs having n nodes, no loops, and constant outdegrees m. An undirected graph \(G_ n(m)\) is obtained by deleting orientations and coalescing muliple edges. It is shown that \(G_ n(m)\) is bicritical as \(n\to \infty\) with a probability tending to 0 for \(m=1\), \((1-2e^{- 2})^{1/2}\) for \(m=2\), and 1 for \(m\geq 3\).
Recommendations
Cites work
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- Limit theorems for complete subgraphs of random graphs
- Maximum matchings in a class of random graphs
- Minimum node covers and 2-bicritical graphs
- Random near-regular graphs and the node packing problem
- The number of matchings in random regular graphs and bipartite graphs
- Threshold functions for small subgraphs
- Vertex packings: Structural properties and algorithms
Cited in
(12)- Random near-regular graphs and the node packing problem
- Maximum matchings in a class of random graphs
- Maximal paths in random dynamic graphs
- Fuzzy intersection graphs
- A proof of the block model threshold conjecture
- Bin-packing and matchings in threshold graphs
- Walks on random digraphs
- Persistency of linear programming relaxations for the stable set problem
- The bin-covering technique for thresholding random geometric graph properties
- Random threshold digraphs
- How tight is the corner relaxation? Insights gained from the stable set problem
- Optimal threshold for a random graph to be 2-universal
This page was built for publication: An exact threshold theorem for random graphs and the node-packing problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095150)
