| Title |
On hamiltonicity of uniform random intersection graphs |
| Translation of Title |
Apie tolygių atsitiktinių sankirtų grafų hamiltoniškumą. |
| Authors |
Bloznelis, Mindaugas ; Radavičius, Irmantas |
| DOI |
10.15388/LMR.2010.80 |
| Full Text |
|
| Is Part of |
Lietuvos matematikos rinkinys. LMD darbai.. Vilnius : Matematikos ir informatikos institutas. 2010, t. 51, p. 443-447.. ISSN 0132-2818 |
| Keywords [eng] |
Random graph ; Intersection graph ; Hamilton cycle ; Clustering |
| Abstract [eng] |
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(−1)m(lnm+ln lnm+ω(m)) with some ω(m) - +∞ as m - ∞. |
| Published |
Vilnius : Matematikos ir informatikos institutas |
| Type |
Journal article |
| Language |
English |
| Publication date |
2010 |
| CC license |
|
