Open AccessThe independent domination number of a random graph
Author(s) -
Lane Clark,
Darin Johnson
Publication year - 2011
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1533
Subject(s) - mathematics , combinatorics , random graph , graph , notation , domination analysis , discrete mathematics , arithmetic , vertex (graph theory)
We prove a two-point concentration for the independent domination number of the random graph Gn,p provided p 2 ln(n) 64ln((lnn)=p). occurs asymptotically almost surely (a.a.s.) if P(Gn;p has property A) ! 1 as n ! 1 . See Bollobas (2) for notation and terminology. Weber (7) showed if p = 1=2 then a.a.s. (Gn;p) is either blog2 n − log2(log2 nlnn)c + 1 or blog2 n − log2(log2 nlnn)c + 2 and a.a.s. i(Gn;p)
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom