On hamiltonicity of uniform random intersection graphs
Mindaugas Bloznelis
Vilnius University
Irmantas Radavičius
Vilnius University
Published 2010-12-21


random graph
intersection graph
Hamilton cycle

How to Cite

Bloznelis M. and Radavičius I. (2010) “On hamiltonicity of uniform random intersection graphs”, Lietuvos matematikos rinkinys, 51(proc. LMS), pp. 443–447. doi: 10.15388/LMR.2010.80.


We give a sufficient condition for the hamiltonicity of the uniform random intersection graph G{n,m,d}. It is a graph on n vertices, where each vertex is assigned d keys drawn independently at random from a given set of m keys, and where any two vertices establish an edge whenever they share at least one common key. We show that with probability tending to 1 the graph Gn,m,d has a Hamilton cycle provided that n = 2-1m(ln m + ln ln m + ω(m)) with some ω(m) → +∞ as m → ∞.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Please read the Copyright Notice in Journal Policy