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/

[1] S. Akbari, M. Khatirinejad and S. Qajar, A note on the Roman bondage number of planar graphs, Graphs Combin. 29 (2013) 327–331. doi:10.1007/s00373-011-1129-8

[2] A. Bahremandpour, F.-T. Hu, S.M. Sheikholeslami and J.-M. Xu, On the Roman bondage number of a graph, Discrete Math. Algorithms Appl. 5 (2013) #1350001. doi:10.1142/S1793830913500018

[3] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575–1586. doi:10.1137/070699688

[4] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A.A. McRae, Roman {2}- domination, Discrete Appl. Math. 204 (2016) 22–28. doi:10.1016/j.dam.2015.11.013

[5] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22. doi:10.1016/j.disc.2003.06.004

[6] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47–57. doi:10.1016/0012-365X(90)90348-L

[7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, 1979).

[8] J. Kleinberg and E. Tardos, Algorithm Design (Pearson Education, India, 2006).

[9] P. Roushini Leely Pushpam and T.N.M. Malini Mai, Weak roman domination in graphs, Discuss. Math. Graph Theory 31 (2011) 115–128. doi:10.7151/dmgt.1532

[10] N. Jafari Rad and L. Volkmann, Roman bondage in graphs, Discuss. Math. Graph Theory 31 (2011) 763–773. doi:10.7151/dmgt.1578

[11] M. Krzywkowski, 2 -bondage in graphs, Int. J. Comput. Math. 90 (2013) 1358–1365. doi:10.1080/00207160.2012.752817

[12] T. Turaci, On the average lower bondage number of a graph, RAIRO Oper. Res. 50 (2016) 1003–1012. doi:10.1051/ro/2015062