On the bondage number of planar and directed graphs

AbstractThe bondage number b(G) of a nonempty graph G is defined to be the cardinality of the smallest set E of edges of G such that the graph G-E has domination number greater than that of G. In this paper we present a simple, intuitive proof that b(G)⩽min{8,Δ(G)+2} for all planar graphs G, give examples of planar graphs with bondage number 6, and bound the bondage number of directed graphs