Anzeige
Erschienen in:
1990 | OriginalPaper | Buchkapitel
On the Radius of Random Subgraphs of the n-Cube
verfasst von : K. Mahrhold, K. Weber
Erschienen in: Topics in Combinatorics and Graph Theory
Verlag: Physica-Verlag HD
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.