Advertisement
Published in:
1990 | OriginalPaper | Chapter
On the Radius of Random Subgraphs of the n-Cube
Authors : K. Mahrhold, K. Weber
Published in: Topics in Combinatorics and Graph Theory
Publisher: Physica-Verlag HD
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Dyer, Frieze and Foulds (cf. [1_]) introduced a general model of random subgraphs Gn of the n-cube graph Qn. We determine the radius R(Gn) of these random subgraphs Gn of Qn for fixed probabilities pv, pe satisfying 1/2 ≤ Pv pe< 1: With probability tending to one as n tends to infinity we haveR(Gn) = n − 1 if 1/2<Pv<1,R(Gn) = n if Pv = 1 and Pe>1/2,n − 1 ≤ R(Gn) ≤ n if Pv = 1 and Pe = 1/2 andn − 2 ≤ R(Gn) ≤ n − 1 if Pv = 1/2 and Pe = 1.