On hamiltonicity of uniform random intersection graphs

Abstract

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 → ∞.

Keywords

• random graph
• intersection graph
• Hamilton cycle
• clustering