Strong and weak cobondage numbers of a graph
P. Thangaraju · Journal of Information and Optimization Sciences · 2018
Let G = (V, E) be a graph. If uv ∈ E, we say that u and v dominate each other. If uv ∈ E and deg u ≥ deg v, we say that u strongly dominates v and v weakly dominates u. A subset D of V is called a strong dominating set of G if every vertex v ∈ V – D is strongly dominated by some u ∈ D. The strong domination number γs(G) of G is the size of its smallest strong dominating set. Similarly, a weak dominating set and the weak domination number γw(G) of G are defined. We define the strong cobondage number bsc(G) of G to be the minimum number of edges to be added to G to decrease the strong domination number γs(G). Similarly, we define weak cobondage number bwc(G) of G. In this paper, strong and weak cobondage numbers of some standard graphs are found. Upper bounds for bsc(G) and bwc(G) for trees are obtained; also graphs attaining these bounds are characterised. Upper bounds for bsc(G) in terms of D(G) and n are given and graphs that attain these bounds are established. An upper bound for bwc is determined for any graph G. An upper bound for bsc(G) + γs(G) is found and graphs that attain these bounds are characterised.