research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:chita
TitleOn the Independence Number and Hamiltonicity of Uniform Random Intersection Graphs
Bibtex cite IDRACTI-RU1-2011-49
Journal Theoretical Computer Science
Year published 2011
Volume 412
Number 48
Pages 6750-6760
DOI 10.1016/j.tcs.2011.09.003
Keywords random graphs,intersection graphs,independent set,hamiltonian cycle,probabilistic methods
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.
Nikoletseas, Sotiris
Raptopoulos, Christoforos
Spirakis, Paul
nikole.pdf (main file)
Publication ID901