On $k$-connectivity and minimum vertex degree in random $s$-intersection graphs

Jun Zhao, Osman Yağan, Virgil Gligor

Published 2014-09-21Version 1

Random s-intersection graphs have recently received much interest [1-9]. In a random s-intersection graph, each vertex is assigned to a set of items in some manner, and two vertices have an edge in between if and only if they share at least s items. In particular, in a uniform random s-intersection graph, each vertex independently selects the same number of items uniformly at random from a common item pool, while in a binomial random s-intersection graph, each item in some item pool is independently attached to each vertex with the same probability. These two graph models have numerous applications; e.g., using uniform random s-intersection graph for cryptanalysis [14,15], and to model secure wireless sensor networks [8-10] and online social networks [11,12], and using a binomial random s-intersection graph for clustering analysis [17], classification [18] and the design of integrated circuits [34]. For binomial/uniform random s-intersection graphs, we present results related to k-connectivity and minimum vertex degree. Specifically, we derive the asymptotically exact probabilities and asymptotic zero-one laws for the following three properties: (i) k-vertex-connectivity, (ii) k-edge-connectivity and (iii) the property of minimum vertex degree being at least k. Recently, similar results have been obtained by Bloznelis and Rybarczyk [5], but their findings are only for uniform random s-intersection graphs, not for binomial random s-intersection graphs, and require parameter conditions which are disjoint from ours - our parameter conditions are useful in practical sensor network applications of the graphs while theirs are not. In terms of binomial s-intersection graphs, for the three properties above, our paper reports the first result on the exact probabilities as well as the first result on the zero-one laws.