A dominating set of a graph is a subset $D$ of its vertices such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number of a graph $G$ is the number of vertices in a smallest dominating set of $G$. The bondage number of a nonempty graph $G$ is the size of a smallest set of edges whose removal from $G$ results in a graph with domination number greater than the domination number of $G$. In this note, we study the bondage number of the binomial random graph $G(n,p)$. We obtain a lower bound that matches the order of the trivial upper bound. As a side product, we give a one-point concentration result for the domination number of $G(n,p)$ under certain restrictions.
@article{10_37236_5180,
author = {Dieter Mitsche and Xavier P\'erez-Gim\'enez and Pawe{\l} Pra{\l}at},
title = {The bondage number of random graphs},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {2},
doi = {10.37236/5180},
zbl = {1335.05162},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5180/}
}
TY - JOUR
AU - Dieter Mitsche
AU - Xavier Pérez-Giménez
AU - Paweł Prałat
TI - The bondage number of random graphs
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5180/
DO - 10.37236/5180
ID - 10_37236_5180
ER -
%0 Journal Article
%A Dieter Mitsche
%A Xavier Pérez-Giménez
%A Paweł Prałat
%T The bondage number of random graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5180/
%R 10.37236/5180
%F 10_37236_5180
Dieter Mitsche; Xavier Pérez-Giménez; Paweł Prałat. The bondage number of random graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5180
