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:Inproceedings
Entered by:
TitleOn the Existence of Hamiltonian Cycles in Random Intersection Graphs
Bibtex cite IDRACTI-RU1-2005-34
Booktitle 32nd International Conference on Automata, Languages and Programming (ICALP 2005)
Year published 2005
Month July
Volume 3580/2005
Pages 690-701
Location Lisboa, Portugal
DOI 10.1007/11523468
Random Intersection Graphs is a new class of random graphs introduced in [5], in which each of n vertices randomly and independently chooses some elements from a universal set, of cardinality m. Each element is chosen with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=ná, for any real á different than one, we establish here, for the first time, tight lower bounds p0(n,m), on the value of p, as a function of n and m, above which the graph Gn,m,p is almost certainly Hamiltonian, i.e. it contains a Hamilton Cycle almost certainly. Our bounds are tight in the sense that when p is asymptotically smaller than p0(n,m) then Gn,m,p almost surely has a vertex of degree less than 2. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection model. Interestingly, Hamiltonicity appears well below the general thresholds, of [4], at which Gn,m,p looks like a usual random graph. Thus our bounds are much stronger than the trivial bounds implied by those thresholds. Our results strongly support the existence of a threshold for Hamiltonicity in Gn,m,p.
Efthymiou, Charilaos
Spirakis, Paul
fulltext.pdf (main file)
Publication ID348