Discussiones Mathematicae Graph Theory 31(1) (2011) 129-142
doi: 10.7151/dmgt.1533

[BIBTex] [PDF] [PS]

THE INDEPENDENT DOMINATION NUMBER OF A RANDOM GRAPH

Lane Clark  and  Darin Johnson

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

Abstract

We prove a two-point concentration for the independent domination number of the random graph Gn,p provided p2ln(n) ≥ 64ln((lnn)/p).

Keywords: random graph, two-point concentration, independent domination.

2010 Mathematics Subject Classification: 05C80, 05C69.

References

[1] N. Alon and J. Spencer, The Probabilistic Method (John Wiley, New York, 1992).
[2] B. Bollobás, Random Graphs (Second Edition, Cambridge University Press, New York, 2001).
[3] 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.
[4] A. Godbole and B. Wieland, On the domination number of a Random graph, Electronic J. Combin. 8 (2001) 1-13.
[5] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
[6] T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998).
[7] K. Weber, Domination number for almost every graph, Rostocker Matematisches Kolloquium 16 (1981) 31-43.

Received 2 March 2010
Accepted 13 April 2010