Non-isolating Bondage in Graphs
Marcin Krzywkowski · Bulletin of the Malaysian Mathematical Sciences Society · 2015
A dominating set of a graph $$G = (V,E)$$ is a set D of vertices of G such that every vertex of $$V(G){\setminus }D$$ has a neighbor in D. The domination number of a graph G, denoted by $$\gamma (G)$$ , is the minimum cardinality of a dominating set of G. The non-isolating bondage number of G, denoted by $$b'(G)$$ , is the minimum cardinality among all sets of edges $$E' \subseteq E$$ such that $$\delta (G-E') \ge 1$$ and $$\gamma (G-E') > \gamma (G)$$ . If for every $$E' \subseteq E$$ we have $$\gamma (G-E') = \gamma (G)$$ or $$\delta (G-E') = 0$$ , then we define $$b'(G) = 0$$ , and we say that G is a $$\gamma $$ -non-isolatingly strongly stable graph. First we discuss various properties of non-isolating bondage in graphs. We find the non-isolating bondage numbers for several classes of graphs. Next we show that for every non-negative integer, there exists a tree having such non-isolating bondage number. Finally, we characterize all $$\gamma $$ -non-isolatingly strongly stable trees.