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 Qn(k). Let k be an integer, 1 ≤ k ≤ n-1. We let Qn(k) be the graph that is generated by independently including for every ν ∊ V(Qn) a set of k distinct edges chosen uniformly from all the (k n) sets of distinct edges that are incident to ν. We study the connectivity properties of Qn(k) as k varies. We show that without high probability (w.h.p.), Qn(1) does not contain a giant component i.e., a component that spans Ω(2n) vertices. Thereafter, we show that such a component emerges when k=2. In addition, the giant component spans all but o(2n) vertices, and hence it is unique. We then establish the connectivity threshold found at k0=log2 n-2log2log2 n. The threshold is sharp in the sense that Qn([k0]) is disconnected but Qn([k0]+1) is connected w.h.p. Furthermore, we show that w.h.p., Qn(k) is k-connected for every k≥ [k0]+1. [ABSTRACT FROM AUTHOR]