Bahremandpour, A.; Hu, Fu-Tao; Sheikholeslami, S. M.; Xu, Jun-Ming On the Roman bondage number of a graph. (English) Zbl 1268.05143 Discrete Math. Algorithms Appl. 5, No. 1, 1350001, 15 p. (2013). Summary: A Roman dominating function (RDF) on a graph \(G= (V,E)\) is a function \(f: V \to \{0,1\}\) such that every vertex \(v \in V\) with \(f(v)= 0\) has at least one neighbor \(a \in V\) with \(f(a) = 2\). The weight of a RDF is the value \(f(V(G)) = \sum_{u\in V(G)} f(u)\). The minimum weight of a RDF on a graph \(G\) is called the Roman domination number, denoted by \(b_R(G)\). The Roman bondage number \(b_R(G)\) of a graph \(G\) with maximum degree at least two is the minimum cardinality of all sets \(E' \subseteq E(G)\) for which \(\gamma_R(G-E') > \gamma_R(G)\).In this paper, we first show that the decision problem for determining \(b_R(G)\) is NP-hard even for bipartite graphs and then we establish some sharp bounds for \(b_R(G)\) and characterizes all graphs attaining some of these bounds. Cited in 9 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:Roman domination number; Roman bondage number; NP-hardness PDFBibTeX XMLCite \textit{A. Bahremandpour} et al., Discrete Math. Algorithms Appl. 5, No. 1, 1350001, 15 p. (2013; Zbl 1268.05143) Full Text: DOI arXiv References: [1] DOI: 10.1002/net.3230180304 · Zbl 0658.05042 · doi:10.1002/net.3230180304 [2] DOI: 10.1137/070699688 · Zbl 1207.05135 · doi:10.1137/070699688 [3] DOI: 10.1016/j.disc.2003.06.004 · Zbl 1036.05034 · doi:10.1016/j.disc.2003.06.004 [4] Cockayne E. J., Bull. Inst. Combin. Appl. 39 pp 87– [5] Dehgardi N., AKCE Int. J. Graphs Comb. 8 pp 169– [6] Ebadi K., Int. J. Contemp. Math. Sci. 5 pp 1487– [7] DOI: 10.1016/j.disc.2008.09.043 · Zbl 1191.05071 · doi:10.1016/j.disc.2008.09.043 [8] DOI: 10.1016/0012-365X(90)90348-L · Zbl 0745.05056 · doi:10.1016/0012-365X(90)90348-L [9] Fu X. L., Discrete Math. 309 pp 1528– [10] Garey M. R., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) · Zbl 0411.68039 [11] DOI: 10.1016/j.disc.2007.10.016 · Zbl 1186.05091 · doi:10.1016/j.disc.2007.10.016 [12] Haynes T. W., Fundamentals of Domination in Graphs (1998) · Zbl 0890.05002 [13] Haynes T. W., Domination in Graphs: Advanced Topics (1998) · Zbl 0883.00011 [14] Henning M. A., Discuss. Math. Graph Theory 22 pp 225– [15] DOI: 10.1016/S0012-365X(03)00040-2 · Zbl 1022.05055 · doi:10.1016/S0012-365X(03)00040-2 [16] DOI: 10.1016/S0012-365X(02)00811-7 · Zbl 1024.05068 · doi:10.1016/S0012-365X(02)00811-7 [17] DOI: 10.1016/j.jco.2011.11.001 · Zbl 1239.05138 · doi:10.1016/j.jco.2011.11.001 [18] DOI: 10.1007/11604686_10 · doi:10.1007/11604686_10 [19] DOI: 10.1016/j.dam.2008.01.011 · Zbl 1180.05113 · doi:10.1016/j.dam.2008.01.011 [20] Rad N. J., Discuss. Math. Graph Theory 31 pp 763– [21] Rad N. J., Graphs Comb. 27 pp 531– [22] DOI: 10.2307/2589113 · Zbl 1039.90038 · doi:10.2307/2589113 [23] DOI: 10.1016/j.disc.2007.03.020 · Zbl 1127.05075 · doi:10.1016/j.disc.2007.03.020 [24] DOI: 10.1007/978-3-540-72588-6_51 · Zbl 05293784 · doi:10.1007/978-3-540-72588-6_51 [25] DOI: 10.1142/S1793830910000504 · Zbl 1209.68652 · doi:10.1142/S1793830910000504 [26] DOI: 10.1038/scientificamerican1299-136 · doi:10.1038/scientificamerican1299-136 [27] DOI: 10.1016/0166-218X(94)90110-4 · Zbl 0803.05049 · doi:10.1016/0166-218X(94)90110-4 [28] West D. B., Introduction to Graph Theory (2000) [29] DOI: 10.1016/j.disc.2006.06.018 · Zbl 1108.05072 · doi:10.1016/j.disc.2006.06.018 [30] DOI: 10.1007/978-1-4757-3387-7 · doi:10.1007/978-1-4757-3387-7 [31] DOI: 10.1007/978-1-4419-8698-6 · Zbl 1035.05003 · doi:10.1007/978-1-4419-8698-6 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.