On Emergence of Dominating Cliques in Random Graphs

Details On Emergence of Dominating Cliques in Random Graphs On Emergence of Dominating Cliques in Random Graphs

2008-05-14

arxiv.org/abs/0805.2105v1

Mathematics

Combinatorics

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

Scientific paper

Emergence of dominating cliques in Erd\"os-R\'enyi 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$.

Affiliated with

Also associated with

No associations

Rating

On Emergence of Dominating Cliques in Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Emergence of Dominating Cliques in Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Emergence of Dominating Cliques in Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56147