Connectivity properties of random geometric irrigation graphs
Gábor Lugosi (Univ. Pompeu Fabra)
Consider a graph whose vertices represent n uniform random points in the unit square. One may form a random geometric graph by connecting two points by an edge if the distance of the points is at most r. Let c be a positive integer. We form an irrigation subgraph of the random geometric graph by selecting, at random, c vertices among the neighbors of any given vertex, and keeping only the edges joining the vertex to the selected neighbors. We present various results about connectivity properties of such
graphs. Joint work with Nicolas Broutin and Luc Devroye.