Extreme degrees in random subgraphs of regular graphs

From MaRDI portal





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.











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)