Geodesic
Roman {2}-Bondage Number of a Graph
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 255-268

Voir la notice de l'article provenant de la source Library of Science

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 Σu∈V (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, bR2, is defined as the cardinality of a smallest edge set E′ ⊆ E for which γR2(G − E′) gt; γ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.
Keywords: domination, Roman {2}-domination, Roman {2}-bondage number 
@article{DMGT_2020_40_1_a16,
     author = {Moradi, Ahmad and Mojdeh, Doost Ali and Sharifi, Omid},
     title = {Roman {{2}-Bondage} {Number} of a {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {255--268},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a16/}
}
TY  - JOUR
AU  - Moradi, Ahmad
AU  - Mojdeh, Doost Ali
AU  - Sharifi, Omid
TI  - Roman {2}-Bondage Number of a Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 255
EP  - 268
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a16/
LA  - en
ID  - DMGT_2020_40_1_a16
ER  - 
%0 Journal Article
%A Moradi, Ahmad
%A Mojdeh, Doost Ali
%A Sharifi, Omid
%T Roman {2}-Bondage Number of a Graph
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 255-268
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a16/
%G en
%F DMGT_2020_40_1_a16
Moradi, Ahmad; Mojdeh, Doost Ali; Sharifi, Omid. Roman {2}-Bondage Number of a Graph. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 255-268. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a16/