The Bondage Number of \((n-3)\)-Regular Graphs of Order \(n\)

Abstract

Let \(G = (V, E)\) be a graph. A subset \(D \subseteq V\) is a dominating set if every vertex not in \(D\) is adjacent to a vertex in \(D\). The domination number of \(G\) is the smallest cardinality of a dominating set of \(G\). The bondage number of a nonempty graph \(G\) is the smallest number of edges whose removal from \(G\) results in a graph with larger domination number than \(G\). In this paper, we determine that the exact value of the bondage number of an \((n-3)\)-regular graph \(G\) of order \(n\) is \(n-3\).