Bounds on the bondage number of a graph (Q1322182)

The bondage number \(b(G)\) of a graph \(G\) is the minimum cardinality of a set of edges of \(G\) whose removal from \(G\) results in a graph with domination number larger than that of \(G\). In this paper several new sharp upper bounds for \(b(G)\) are established and an infinite class of graphs each of whose bondage number is greater than its maximum degree plus one is presented. This shows that Fink's conjecture is incorrect.