On the bondage number of a graph (Q1126221): Difference between revisions

The paper concerns the bondage number of a graph. This number is closely related to the domination number. A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating, if for each \(x\in V(G)-D\) there exists a vertex \(y\in D\) adjacent to \(x\). The minimum number of vertices of a dominating set in \(G\) is called the domination number \(\gamma(G)\) of \(G\). The bondage number \(b(G)\) of \(G\) is the minimum number of vertices whose deletion makes \(\gamma(G)\) increase; it was introduced by \textit{J. F. Fink}, \textit{M. S. Jacobson}, \textit{L. F. Kinch} and \textit{J. Roberts} [Discrete Math. 86, No. 1-3, 47-57 (1990; Zbl 0745.05056)]. The main result of the paper is finding an upper bound for \(b(G)\).