Paired bondage in trees

Let G = (V, E) be a graph with delta(G) >= 1. A set D subset of V is a paired dominating set if D is dominating, and the induced subgraph < D > contains a perfect matching. The paired domination number of G, denoted by gamma(p)(G), is the minimum cardinality of a paired dominating set of G. The paired bondage number, denoted by b(p)(G), is the minimum cardinality among all sets of edges E' subset of E such that delta(G - E') >= 1 and gamma(p)(G - E') > gamma(p)(G). We say that G is a gamma(p)-strongly stable graph if, for all E' subset of E, either gamma(p)(G - E') = gamma(p)(G) or delta(G - E') = 0. We discuss the basic properties of paired bondage and give a constructive characterization of gamma(p)-strongly stable trees. (C) 2007 Elsevier B.V. All rights reserved.