On hamiltonicity of uniform random intersection graphs - Bloznelis, Mindaugas; Radavičius, Irmantas (Lietuvos matematikos rinkinys, 2010)
We give a sufficient condition for the hamiltonicity of the uniform random intersection graph Gn,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 → ∞.