DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

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