The independent domination number of a random graph

ArticleOriginal scientific text

Title

Authors ¹, ¹

Department of Mathematics, Southern Illinois University Carbondale, Carbondale, IL 62901-4408, USA

We prove a two-point concentration for the independent domination number of the random graph

G_{n, p}

provided p²ln(n) ≥ 64ln((lnn)/p).

random graph, two-point concentration, independent domination

N. Alon and J. Spencer, The Probabilistic Method (John Wiley, New York, 1992).
B. Bollobás, Random Graphs (Second Edition, Cambridge University Press, New York, 2001).
A. Bonato and C. Wang, A note on domination parameters in random graphs, Discuss. Math. Graph Theory 28 (2008) 307-322, doi: 10.7151/dmgt.1409.
A. Godbole and B. Wieland, On the domination number of a Random graph, Electronic J. Combin. 8 (2001) 1-13.
T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998).
K. Weber, Domination number for almost every graph, Rostocker Matematisches Kolloquium 16 (1981) 31-43.