2012 | OriginalPaper | Chapter
A Detailed Study of the Dominating Cliques Phase Transition in Random Graphs
Authors : Martin Nehéz, Daniel Olejár, Michal Demetrian
Published in: Theory and Applications of Models of Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A subset of nodes
S
⊆
V
of a graph
G
= (
V
,
E
) is a dominating clique if
S
is a dominating set and a clique of
G
. The phase transition of dominating cliques in Erdös-Rényi random graph model
is investigated in this paper. Lower and upper bounds on the edge probability
p
for the existence of an
r
-node dominating clique are established in this paper. We prove therein that given an
n
-node random graph
G
from
for
r
=
c
log
1/
p
n
with 1 ≤
c
≤ 2 it holds: (1) if
p
> 1/2 then an
r
-clique is dominating in
G
with a high probability and, (2) if
$p \leq ( 3 - \sqrt{5})/2$
then an
r
-clique is not dominating in
G
with a high probability. The remaining range of the probability
p
is discussed with more attention. Within such a range, we provide intervals of
r
where a dominating clique existence probability is zero, positive but less than one, and one, respectively.