PDF
Discussiones Mathematicae Graph Theory 31(1) (2011)
129-142
DOI: https://doi.org/10.7151/dmgt.1533
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
Close