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

DOI10.1016/0095-8956(86)90076-6zbMath0632.05031OpenAlexW2127277012MaRDI QIDQ1095150

Geoffrey 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

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

Related Items

Maximum matchings in a class of random graphs, Fuzzy intersection graphs, How tight is the corner relaxation? Insights gained from the stable set problem, Random near-regular graphs and the node packing problem, Persistency of linear programming relaxations for the stable set problem

Cites Work

• Unnamed Item
• Random near-regular graphs and the node packing problem
• The number of matchings in random regular graphs and bipartite graphs
• Maximum matchings in a class of random graphs
• Limit theorems for complete subgraphs of random graphs
• Minimum node covers and 2-bicritical graphs
• Threshold functions for small subgraphs
• Vertex packings: Structural properties and algorithms