Publications and Preprints

Size of the Giant Component in a Random Geometric Graph
Ghurumuruhan Ganesan
In this paper, we study the size of the giant component \(C_G\) in the random geometric graph \(G = G(n,r_n, f)\) of \(n\) nodes independently distributed each according to a certain density \(f(.)\) in \([0,1]^2\) satisfying \(\inf_{x \in [0,1]^2} f(x)~>\)~\(0.\) If \(\frac{c_1}{n} \leq r_n^2 \leq c_2\frac{\log{n}}{n}\) for some positive constants \(c_1, c_2\) and \(nr_n^2 \longrightarrow \infty,\) we show that %for some positive numbers \(\epsilon_1\) sufficiently large and \(\epsilon_2,\) the giant component of \(G\) contains at least \(n - o(n)\) nodes with probability at least \(1 - o(1)\) as \(n \rightarrow \infty.\) We also obtain estimates on the diameter and number of the non-giant components of \(G.\)

isid/ms/2012/13 [fulltext]

Click here to return to Preprints Page