CONNECTIVITY PROPERTIES OF RANDOM SUBGRAPHS OF THE CUBE

The n-dimensional cube Q(n) is the graph whose vertices are the subset s of{1,..,n} where two such vertices are adjacent if and only if their symmetric difference is a singleton. Clearly Q(n) is an n-connected g raph of diameter and radius n. Write M = n2n(-1) = e(Q(n)) for the siz e of Q(n). Let (Q) over tilde = (Q(t))(0)(M) be a random Q(n)-process. Thus and, is a spanning subgraph of Q(n) of size t, and Q(t), is obta ined from Q(t-1), by the random addition of an edge of Q(n) not in Q(t -1). Let t((k)) = tau((Q) over tilde; delta greater than or equal to k ) be the hitting time of the property of having minimal degree at leas t k. It is shown in [5] that, almost surely, at time t((1)) the graph Q(t) becomes connected and that in fact the diameter of Q(t), at this point is n + 1. Here we generalize this result by showing that, for an y fixed k greater than or equal to 2, almost surely at time t((k)) the graph Q(t), acquires the extremely strong property that any two of it s vertices are connected by k internally vertex-disjoint paths each of length at most n, except for possibly one, which may have length n 1. In particular, the hitting time of k-connectedness is almost surely t((k)). (C) 1995 John Wiley and Sons, Inc.