Random subcube intersection graphs I: cliques and covering
2016 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 23, no 3, P3.43Article in journal (Refereed) Published
We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube Qd to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model 'random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube Qd and for the appearance of s-cliques. In addition we pose a number of open problems.
Place, publisher, year, edition, pages
2016. Vol. 23, no 3, P3.43
Random graphs, Random intersection graphs
IdentifiersURN: urn:nbn:se:umu:diva-127244ISI: 000385228700002OAI: oai:DiVA.org:umu-127244DiVA: diva2:1046590