Connectivity of the k-out Hypercube

Abstract

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\le k\le n-1$. We let $Q^n(k)$ be the graph that is generated by independently including for every $v\in V(Q^n)$ a set of $k$ distinct edges chosen uniformly from all the $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ sets of distinct edges that are incident to $v$. We study connectivity the properties of $Q^n(k)$ as $k$ varies. We show that w.h.p. $Q^n(1)$ does not contain a giant component i.e. a component that spans $\Omega (2^n)$ 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(\lfloor k_0\rfloor )$ is disconnected but $Q^n(\lceil k_0\rceil +1)$ is connected w.h.p. Furthermore we show that w.h.p. $Q^n(k)$ is $k$-connected for every $k\ge \lceil k_0\rceil +1$.