Roman { 2}-bondage number of a graph
Doost Ali Mojdeh, Ahmad Moradi, Omid Sharifi · Discussiones Mathematicae Graph Theory · 2018
For a given graph G = (V, E), a Roman {2}-dominating function f : V (G) {0, 1, 2} has the property that for every vertex u with f (u) = 0, either u is adjacent to a vertex assigned 2 under f , or is adjacent to at least two vertices assigned 1 under f . The Roman {2}-domination number of G, {R2} (G), is the minimum of uV (G) f (u) over all such functions. In this paper, we initiate the study of the problem of finding Roman {2}-bondage number of G. The Roman {2}-bondage number of G, b {R2} , is defined as the cardinality of a smallest edge set E E for which {R2} (G -E ) > {R2} (G). We first demonstrate complexity status of the problem by proving that the problem is NP-Hard. Then, we derive useful parametric as well as fixed upper bounds on the Roman {2}-bondage number of G. Specifically, it is known that the Roman bondage number of every planar graph does not exceed 15 (see [S. Akbari, M. Khatirinejad and S. Qajar, A note on the Roman bondage number of planar graphs, Graphs Combin. 29 (2013) 327-331]). We show that same bound will be preserved while computing the Roman {2}-bondage number of such graphs. The paper is then concluded by computing exact value of the parameter for some classes of graphs.