On Emergence of Dominating Cliques in Random Graphs

Abstract

Emergence of dominating cliques in Erdös-Rényi random graph model ${\bbbg(n,p)}$ is investigated in this paper. It is shown this phenomenon possesses a phase transition. Namely, we have argued that, given a constant probability $p$, an $n$-node random graph $G$ from ${\bbbg(n,p)}$ and for $r=c{\log }_{1/p}n$ with $1\le c\le 2$, it holds: (1) if $p>1/2$ then an $r$-node clique is dominating in $G$ almost surely and, (2) if $p\le (3-\sqrt{5})/2$ then an $r$-node clique is not dominating in $G$ almost surely. The remaining range of probability $p$ is discussed with more attention. A detailed study shows that this problem is answered by examination of sub-logarithmic growth of $r$ upon $n$.

to appear in Proc. 2nd Int. Conf. on Math. and Applications in Information Technology, Lahore Univ. of Management, Lahore, Pakistan, 2008