On hamiltonicity of uniform random intersection graphs
Articles
Mindaugas Bloznelis
Vilnius University
Irmantas Radavičius
Vilnius University
Published 2010-12-21
https://doi.org/10.15388/LMR.2010.80
PDF

Keywords

random graph
intersection graph
Hamilton cycle
clustering

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.

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

PDF

Downloads

Download data is not yet available.