We consider a random geometric (undirected) graph $G=(V,E)$ ($n=|V|$):
- to each vertex $u \in V=\{0,\ldots,n-1\}$ a random point $P(u) \in [a;b]^2$ is associated.
- two vertices $u$ and $v$ are connected iff $|P(u)-P(v)|\le 1$.
Let $N(u)=\{v\in V, (u, v) \in E\}$.
Then we construct $A \subset V$ with the following algorithm:
- Initialization: $m(u)=0$ for all $u\in V$.
- For all vertex $u$, let $B_u=\{v\in N(u),v \le u\}$. If $B_u$ is connected and $N(u)\subset N(B_u)$, then $m(u)=1$.
- Let $A = \{u\in V, m(u)=0\}$.
So far it's easy to see that $A$ is a dominating set of $G$. Now I'd like to analyze the average size of $A$ as $n \to \infty$. I guess that the goal is to construct a small dominating set (in average). Any advice?