Discussiones Mathematicae Graph Theory 28(2) (2008)
335-343
DOI: https://doi.org/10.7151/dmgt.1409
A NOTE ON DOMINATION PARAMETERS IN RANDOM GRAPHS
Anthony Bonato
Department of Mathematics | Changping Wang
Department of Mathematics |
Abstract
Domination parameters in random graphs G(n,p), where p is a fixed real number in (0,1), are investigated. We show that with probability tending to 1 as n→ ∞, the total and independent domination numbers concentrate on the domination number of G(n,p).Keywords: domination, random graphs, independent domination, total domination.
2000 Mathematics Subject Classification: 05C69, 05C80.
References
[1] | N. Alon and J. Spencer, The Probabilistic Method (Wiley, New York, 2000). |
[2] | P.A. Dreyer, Applications and variations of domination in graphs, Ph.D. Dissertation, Department of Mathematics (Rutgers University, 2000). |
[3] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). |
[4] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). |
[5] | S. Janson, T. Łuczak and A. Ruciński, Random Graphs (John Wiley and Sons, New York, 2000), doi: 10.1002/9781118032718. |
[6] | C. Kaiser and K. Weber, Degrees and domination number of random graphs in the n-cube, Rostock. Math. Kolloq. 28 (1985) 18-32. |
[7] | K. Weber, Domination number for almost every graph, Rostock. Math. Kolloq. 16 (1981) 31-43. |
[8] | B. Wieland and A.P. Godbole, On the domination number of a random graph, The Electronic Journal of Combinatorics 8 (2001) #R37. |
[9] | I.E. Zverovich and V.E. Zverovich, The domination parameters of cubic graphs, Graphs and Combinatorics 21 (2005) 277-288, doi: 10.1007/s00373-005-0608-1. |
Received 11 January 2008
Revised 3 March 2008
Accepted 3 March 2008
Close