Extreme degrees in random subgraphs of regular graphs
The most common probability distribution used for random labelled n- vertex graphs is the one associated with the experiment of independently retaining or deleting the edges of the complete graph on \(\{\) 1,...,n\(\}\), with probabilities p and \(q=1-p\), respectively. In a previous paper by the author and \textit{A. Rucinski} (to appear) and in this sequel one takes up a generalization, in which the complete graph is replaced by an arbitrary d-regular simple graph. Both p and d are functions of n. The special case \(d=n-1\) gives the complete graph as initial graph. In a series of papers referred to in this paper's bibliography, Bollobas obtained many results on the behavior of the maximum and minimum vertex degrees in the case \(d=n-1\). Here the author obtains similar results for the more general case. As in the special case, the most notable feature of the behavior of the extreme vertex degrees is that they are confined with high probability to sets of only two values. Among the theorems in this paper are various sets of conditions under which such confinement obtains; these conditions involve the slow growth of d as a function of n and restrictions on p in terms of d and n. Another theorem shows that if d grows sufficiently slowly but pd remains sufficiently large, then asymptotically the maximum and minimum degrees coincide. Further results concern the case in which p is fixed; in this case under certain conditions, the maximum and minimum vertex degrees again coincide asymptotically, at values near pd.
- Extreme degrees in random graphs
- Extremal subgraphs of random graphs
- Extremal subgraphs of random graphs
- On extremal subgraphs of random graphs
- Some remarks about extreme degrees in a random graph
- scientific article; zbMATH DE number 4048746
- Subgraphs of random graphs with specified degrees
- Extremal results in random graphs
- Subgraphs of dense random graphs with specified degrees
- On the distribution of the maximum k-degrees of the binomial random graph
- Sandwiching dense random regular graphs between binomial random graphs
- On asymptotic properties of Bell polynomials and concentration of vertex degree of large random graphs
- Degrees in link graphs of regular graphs
- Random regular graphs of high degree
- Focusing of maximum vertex degrees in random faulty scaled sector graphs
- Some remarks about extreme degrees in a random graph
- scientific article; zbMATH DE number 4048746 (Why is no real title available?)
- Extreme degrees in random graphs
- On subgraphs with degrees of prescribed residues in the random graph
- On random irregular subgraphs
- A note on the distribution of the extreme degrees of a random graph via the Stein-Chen method
- Automorphisms of random graphs with specified vertices
This page was built for publication: Extreme degrees in random subgraphs of regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3218859)