An exact threshold theorem for random graphs and the node-packing problem

DOI10.1016/0095-8956(86)90076-6MaRDI QIDQ1095150zbMATH OpenOpenAlexFDO

Authors G. R. Grimmett

Publication date 1986

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(86)90076-6

zbMATH Keywords

random digraphnode packing

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Random near-regular graphs and the node packing problem
• scientific article; zbMATH DE number 3168330
• Maximum matchings in a class of random graphs
• A critical point for random graphs with a given degree sequence
• scientific article; zbMATH DE number 4029600

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)

• Maximum matchings in a class of random graphs
• A proof of the block model threshold conjecture
• Random threshold digraphs
• Fuzzy intersection graphs
• Maximal paths in random dynamic graphs
• Persistency of linear programming relaxations for the stable set problem
• How tight is the corner relaxation? Insights gained from the stable set problem
• The bin-covering technique for thresholding random geometric graph properties
• Walks on random digraphs
• Random near-regular graphs and the node packing problem
• Bin-packing and matchings in threshold graphs
• 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)