Skip to main content
Top

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.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
A Detailed Study of the Dominating Cliques Phase Transition in Random Graphs
Authors
Martin Nehéz
Daniel Olejár
Michal Demetrian
Copyright Year
2012
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-29952-0_55

Premium Partner