  Random key graphs represent topologies of secure wireless sensor networks
that apply the seminal Eschenauer-Gligor random key predistribution scheme to
secure communication between sensors. These graphs have received much attention
and also been used in diverse application areas beyond secure sensor networks;
e.g., cryptanalysis, social networks, and recommender systems. Formally, a
random key graph with $n$ nodes is constructed by assigning each node $X_n$
keys selected uniformly at random from a pool of $Y_n$ keys and then putting an
undirected edge between any two nodes sharing at least one key. Considerable
progress has been made in the literature to analyze connectivity and
$k$-connectivity of random key graphs, where $k$-connectivity of a graph
ensures connectivity even after the removal of $k$ nodes or $k$ edges. Yet, it
still remains an open question for $k$-connectivity in random key graphs under
$X_n \geq 2$ and $X_n = o(\sqrt{\ln n})$ (the case of $X_n=1$ is trivial). In
this paper, we answer the above problem by providing an exact analysis of
$k$-connectivity in random key graphs under $X_n \geq 2$.

Physics and Society;Discrete Mathematics;Social and Information Networks;Combinatorics;Probability