Random near-regular graphs and the node packing problem

DOI10.1016/0167-6377(85)90024-0zbMath0577.05056OpenAlexW2042833774MaRDI QIDQ1065829

William R. Pulleyblank, Geoffrey R. Grimmett

Publication date: 1985

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(85)90024-0

zbMATH Keywords

stable setrandom graphsindependent setbicritical graphsregularizabilitybiparticityweighted node packing

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Related Items

Maximum matchings in a class of random graphs, An exact threshold theorem for random graphs and the node-packing problem, How tight is the corner relaxation? Insights gained from the stable set problem, The maximum clique problem, Persistency of linear programming relaxations for the stable set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Almost all regular graphs are Hamiltonian
• On the connectivity of random m-orientable graphs and digraphs
• Hamiltonian cycles in random regular graphs
• The number of matchings in random regular graphs and bipartite graphs
• Maximum matchings in a class of random graphs
• An exact threshold theorem for random graphs and the node-packing problem
• One-factor in random graphs based on vertex choice
• Limit theorems for complete subgraphs of random graphs
• On the existence of Hamiltonian cycles in a class of random graphs
• Minimum node covers and 2-bicritical graphs
• A random graph
• Threshold functions for small subgraphs
• Vertex packings: Structural properties and algorithms
• On the integer-valued variables in the linear vertex packing problem