The bondage and connectivity of a graph

AbstractLet G=(V,E) be a simple graph. A subset S of V is a dominating set of G if for any vertex v∈V−S, there exists some vertex u∈S such that uv∈E(G). The domination number, denoted by γ(G), is the cardinality of a minimum dominating set of G. The bondage number, denoted by b(G), is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than γ(G). Dunbar et al. (Bondage, insensitivity and reinforcement, in: T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs—Advanced Topics, Marcel Dekker, New York, 1998, pp. 471–489) conjectured that if G has vertex connectivity κ(G)⩾1, then b(G)⩽Δ(G)+κ(G)−1. In this paper, we provide a counterexample to this conjecture