Random near-regular graphs and the node packing problem
type: Item
instance of: scholarly article
title: Random near-regular graphs and the node packing problem
zbMATH Open document ID: 0577.05056
DOI: 10.1016/0167-6377(85)90024-0
published in: Operations Research Letters
publication date: 1985-01-01T00:00:00Z
review text: The graph G is bicritical if its vertex-set contains at least two elements and after deleting any vertex (and its incident edges) from the original G the remainder has a 2-matching. It is proved that the probability that \(G_ n(m)\) is bicritical tends to either 0 or 1 as n increases to infinity if either \(m=1\) or \(m\geq 3\), respectively, and the limit of the upper bound of this probability is less than 1 in the case \(m=2\). \(G_ n(m)\) is defined here as a graph with n, \(n>1\), vertices in which preliminarily the edges are chosen in m independent trials performed for each vertex in separation with the constant density \((n- 1)^{-1}\), and, finally, multiple edges are merged into single ones.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 3922706
zbMATH Keywords: random graphs
zbMATH Keywords: bicritical graphs
zbMATH Keywords: regularizability
zbMATH Keywords: biparticity
zbMATH Keywords: weighted node packing
zbMATH Keywords: stable set
zbMATH Keywords: independent set
author: G. R. Grimmett
author: William R. Pulleyblank
MaRDI profile type: Publication
full work available at URL: 0167-6377(85)90024-0
OpenAlex ID: W2042833774
cites work: Q3963051
cites work: Threshold functions for small subgraphs
cites work: The number of matchings in random regular graphs and bipartite graphs
cites work: Almost all regular graphs are Hamiltonian
cites work: Q3286850
cites work: On the connectivity of random m-orientable graphs and digraphs
cites work: On the existence of Hamiltonian cycles in a class of random graphs
cites work: Hamiltonian cycles in random regular graphs
cites work: Maximum matchings in a class of random graphs
cites work: Q3342613
cites work: An exact threshold theorem for random graphs and the node-packing problem
cites work: Vertex packings: Structural properties and algorithms
cites work: On the integer-valued variables in the linear vertex packing problem
cites work: Minimum node covers and 2-bicritical graphs
cites work: A random graph
cites work: Limit theorems for complete subgraphs of random graphs
cites work: One-factor in random graphs based on vertex choice
description: scientific article; zbMATH DE number 3922706