Radius and diameter of random subgraphs of the hypercube

A. V. Kostochka, A. A. Sapozhenko, K. Weber

Research output: Contribution to journalArticlepeer-review

Abstract

Let Gn = (Vn, En) be the random subgraph of the n‐cube graph Qn produced as follows: Vn is randomly sampled from the vertex set of Qn so that E{x ∈Vn} = pv independently for each vertex x ∈Qn. Then En is randomly sampled from the set of edges induced by Vn in Qn so that P{(x, y) ∈ En} = pe independently for each induced edge (x, y). Let Pv and pe be fixed probabilities such that 0 < p = pvpe ⩽ 1 and mp = [−1 /log2(1 − p)]. We show that for the radius R(Gn) and the diameter D(Gn) of the main component of Gn almost surely the following inequalities hold (Formula Presented.) . © 1993 John Wiley & Sons, Inc.

Original languageEnglish (US)
Pages (from-to)215-229
Number of pages15
JournalRandom Structures & Algorithms
Volume4
Issue number2
DOIs
StatePublished - 1993
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Radius and diameter of random subgraphs of the hypercube'. Together they form a unique fingerprint.

Cite this