International Journal of Combinatorics
Volume 2011 (2011), Article ID 872703, 9 pages
http://dx.doi.org/10.1155/2011/872703
Research Article

On the Isolated Vertices and Connectivity in Random Intersection Graphs

Yilun Shang

Institute for Cyber Security, The University of Texas at San Antonio, San Antonio, TX 78249, USA

Received 10 January 2011; Accepted 5 April 2011

Academic Editor: Liying Kang

Copyright © 2011 Yilun Shang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

We study isolated vertices and connectivity in the random intersection graph 𝐺 ( 𝑛 , 𝑚 , 𝑝 ) . A Poisson convergence for the number of isolated vertices is determined at the threshold for absence of isolated vertices, which is equivalent to the threshold for connectivity. When 𝑚 = ⌊ 𝑛 𝛼 ⌋ and 𝛼 > 6 , we give the asymptotic probability of connectivity at the threshold for connectivity. Analogous results are well known in Erdős-Rényi random graphs.