Radius and diameter of random subgraphs of the hypercube

Let G n = ( V n , E n ) be the random subgraph of the n ‐cube graph Q n produced as follows: V n is randomly sampled from the vertex set of Q n so that E { x ∈ V n } = p v independently for each vertex x ∈ Q n . Then E n is randomly sampled from the set of edges induced by V n in Q n so that P {( x, y ) ∈ E n } = p e independently for each induced edge ( x, y ). Let P v and p e be fixed probabilities such that 0 < p = p v p e ⩽ 1 and m p = [−1 /log 2 (1 − p )]. We show that for the radius R(G n ) and the diameter D(G n ) of the main component of G n almost surely the following inequalities hold. © 1993 John Wiley & Sons, Inc.