{
  "id": "1409.6021",
  "version": "v1",
  "published": "2014-09-21T17:48:32.000Z",
  "updated": "2014-09-21T17:48:32.000Z",
  "title": "On $k$-connectivity and minimum vertex degree in random $s$-intersection graphs",
  "authors": [
    "Jun Zhao",
    "Osman Yağan",
    "Virgil Gligor"
  ],
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.SI",
    "math.PR",
    "physics.soc-ph"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-21T17:48:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60B20",
      "G.2.2",
      "C.2.1"
    ],
    "keywords": [
      "minimum vertex degree",
      "uniform random s-intersection graph",
      "binomial random s-intersection graph",
      "intersection graphs",
      "secure wireless sensor networks"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.6021Z"
    }
  }
}