Random near-regular graphs and the node packing problem

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)

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Random near-regular 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 Q1065829)