The independent domination number of a random graph

• Autorzy: Lane Clark , Darin Johnson
• Języki publikacji: EN

Abstrakty

EN

We prove a two-point concentration for the independent domination number of the random graph $G_{n,p}$ provided p²ln(n) ≥ 64ln((lnn)/p).

Słowa kluczowe

EN

random graph; two-point concentration; independent domination

Kategorie tematyczne

• 05C80: Random graphs
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2011
• Tom: 31
• Numer: 1
• Strony: 129-142

Daty

wydano

2011

otrzymano

2010-03-02

zaakceptowano

2010-04-13

Twórcy

autor

Lane Clark

• Department of Mathematics, Southern Illinois University Carbondale, Carbondale, IL 62901-4408, USA

autor

Darin Johnson

• Department of Mathematics, Southern Illinois University Carbondale, Carbondale, IL 62901-4408, USA

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1533