The Bondage Number of a Graph \(G\) Can Be Much Greater Than \(\Delta(G)\)

The bondage number \(b(G)\) of a nonempty graph \(G\) was first introduced by Fink, Jacobson, Kinch, and Roberts [3]. In their paper they conjectured that \(b(G) \leq \Delta(G)+1\) for a nonempty graph \(G\). A counterexample for this conjecture was shown in [5]. Beyond it, we show now that there doesn’t exist an upper bound of the following form: \(b(G) \leq \Delta(G)+c\) for any \(c\in\mathbb{N}\).