CONNECTIVITY OF THE k-OUT HYPERCUBE

In this paper, we study the connectivity properties of the random subgraph of the n-cube generated by the k-out model and denoted by Q(n)(k). Let k be an integer, 1 <= k <= n - 1. We let Q(n)(k) be the graph that is generated by independently including for every v is an element of V (Q(n)) a set of k distinct edges chosen uniformly from all the ((n)(k)) sets of distinct edges that are incident to v. We study the connectivity properties of Q(n)(k) as k varies. We show that without high probability (w. h. p.), Q(n)(1) does not contain a giant component i. e., a component that spans \Omega (2n) vertices. Thereafter, we show that such a component emerges when k = 2. In addition, the giant component spans all but o(2(n)) vertices, and hence it is unique. We then establish the connectivity threshold found at k(0) = log(2) n-2 log(2) log(2) n. The threshold is sharp in the sense that Q(n)([k(0)]) is disconnected but Q(n)([k(0)] + 1) is connected w. h. p. Furthermore, we show that w. h. p., Q(n)(k) is k-connected for every k >= [k(0)] + 1.