The random key graph is a random graph naturally associated with the random key predistribution scheme introduced by Eschenauer and Gligor in the context of wireless sensor networks (WSNs). For this class of random graphs, we establish a new version of a conjectured zero-one law for graph connectivity as the number of nodes becomes unboundedly large. The results reported here complement and strengthen recent work on this conjecture by Blackburn and Gerke. In particular, the results are given under conditions which are more realistic for applications to WSNs.
Blackburn and Gerke @cite_17 also succeeded in generalizing the one-law result by Di in a number of directions: Under the additional conditions they showed [Thm. 5] BlackburnGerke that This result is weaker than the one-law in the conjecture )-). However, in the process of establishing ), they also show [Thm. 3] BlackburnGerke that the conjecture does hold in the special case @math for all @math without any constraint on the size of the key pools, say @math or @math . Specifically, the one-law in ) is shown to hold whenever the scaling is done according to with @math . As pointed out by these authors, it is now easy to conclude that the one-law in ) holds whenever @math and @math ; this corresponds to a constraint @math .
@cite_17
2063090892
We study properties of the uniform random intersection graph model G(n,m,d). We find asymptotic estimates on the diameter of the largest connected component of the graph near the phase transition and connectivity thresholds. Moreover we manage to prove an asymptotically tight bound for the connectivity and phase transition thresholds for all possible ranges of d, which has not been obtained before. The main motivation of our research is the usage of the random intersection graph model in the studies of wireless sensor networks.