Abstract | In the uniform random intersection graphs model, denoted by Gn;m;, to each vertex v
we assign exactly randomly chosen labels of some label set M of m labels and we connect every
pair of vertices that has at least one label in common. In this model, we estimate the independence
number (Gn;m;), for the wide, interesting range m = n; < 1 and = O(m1=4). We also prove
the hamiltonicity of this model by an interesting combinatorial construction. Finally, we give a brief
note concerning the independence number of Gn;m;p random intersection graphs, in which each vertex
chooses labels with probability p. |