TY - JOUR
AU - Mindaugas Bloznelis
AU - Irmantas Radavičius
PY - 2010/12/21
Y2 - 2022/05/21
TI - On hamiltonicity of uniform random intersection graphs
JF - Lietuvos matematikos rinkinys
JA - LMR
VL - 51
IS - proc. LMS
SE - Articles
DO - 10.15388/LMR.2010.80
UR - https://www.journals.vu.lt/LMR/article/view/17868
AB - 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 → ∞.
ER -