A note on domination parameters in random graphs
Anthony Bonato ; Changping Wang
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 335-343 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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).

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270563 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1409,
     author = {Anthony Bonato and Changping Wang},
     title = {A note on domination parameters in random graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {335-343},
     zbl = {1156.05040},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1409}
}

Anthony Bonato; Changping Wang. A note on domination parameters in random graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 335-343. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1409/

[000] [1] N. Alon and J. Spencer, The Probabilistic Method (Wiley, New York, 2000). | Zbl 0996.05001

[001] [2] P.A. Dreyer, Applications and variations of domination in graphs, Ph.D. Dissertation, Department of Mathematics (Rutgers University, 2000).

[002] [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002

[003] [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). | Zbl 0883.00011

[004] [5] S. Janson, T. Łuczak and A. Ruciński, Random Graphs (John Wiley and Sons, New York, 2000), doi: 10.1002/9781118032718.

[005] [6] C. Kaiser and K. Weber, Degrees and domination number of random graphs in the n-cube, Rostock. Math. Kolloq. 28 (1985) 18-32. | Zbl 0605.05036

[006] [7] K. Weber, Domination number for almost every graph, Rostock. Math. Kolloq. 16 (1981) 31-43. | Zbl 0476.05067

[007] [8] B. Wieland and A.P. Godbole, On the domination number of a random graph, The Electronic Journal of Combinatorics 8 (2001) #R37. | Zbl 0989.05108

[008] [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. | Zbl 1067.05053