On Emergence of Dominating Cliques in Random Graphs
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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 \leq c \leq 2$, it holds: (1) if $p > 1/2$ then an $r$-node clique is dominating in $G$ almost surely and, (2) if $p \leq (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
to appear in Proc. 2nd Int. Conf. on Math. and Applications in Information Technology, Lahore Univ. of Management, Lahore, Pakistan, 2008