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