A bound on the size of a graph with given order and bondage number Original Research Article

The domination number of a graph is the minimum number of vertices in a set S such that every vertex of the graph is either in S or adjacent to a member of S. The bondage number of a graph G is the cardinality of a smallest set of edges whose removal results in a graph with domination number greater than that of G. We prove that a graph with p vertices and bondage number b has at least p(b + 1)/4 edges, and for each b there is at least one p for which this bound is sharp. © 1999 Elsevier Science B.V. All rights reserved