Geodesic
On the domination number of a random graph
The electronic journal of combinatorics, Tome 8 (2001) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper, we show that the domination number $D$ of a random graph enjoys as sharp a concentration as does its chromatic number $\chi$. We first prove this fact for the sequence of graphs $\{G(n,p_n\},\; n\to\infty$, where a two point concentration is obtained with high probability for $p_n=p$ (fixed) or for a sequence $p_n$ that approaches zero sufficiently slowly. We then consider the infinite graph $G({\bf Z}^+, p)$, where $p$ is fixed, and prove a three point concentration for the domination number with probability one. The main results are proved using the second moment method together with the Borel Cantelli lemma.
DOI : 10.37236/1581
Classification : 05C80, 05C69
Mots-clés : domination number, random graph 
@article{10_37236_1581,
     author = {Ben Wieland and Anant P. Godbole},
     title = {On the domination number of a random graph},
     journal = {The electronic journal of combinatorics},
     year = {2001},
     volume = {8},
     number = {1},
     doi = {10.37236/1581},
     zbl = {0989.05108},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1581/}
}
TY  - JOUR
AU  - Ben Wieland
AU  - Anant P. Godbole
TI  - On the domination number of a random graph
JO  - The electronic journal of combinatorics
PY  - 2001
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1581/
DO  - 10.37236/1581
ID  - 10_37236_1581
ER  - 
%0 Journal Article
%A Ben Wieland
%A Anant P. Godbole
%T On the domination number of a random graph
%J The electronic journal of combinatorics
%D 2001
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1581/
%R 10.37236/1581
%F 10_37236_1581
Ben Wieland; Anant P. Godbole. On the domination number of a random graph. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1581

Cité par Sources :