DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 31(1) (2011) 129-142
DOI: 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