The bondage number of random graphs (Q281604)

Summary: 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 \(\mathcal 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 \(\mathcal G(n,p)\) under certain restrictions.