Theoretical Statistics and Mathematics Unit, ISI Delhi

Size of the Giant Component in a Random Geometric Graph

by 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