On the Roman bondage number of a graph

Abstract

A Roman dominating function on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ such that every vertex $v\in V$ with $f(v)=0$ has at least one neighbor $u\in V$ with $f(u)=2$. The weight of a Roman dominating function is the value $f(V(G))={\sum }_{u\in V(G)}f(u)$. The minimum weight of a Roman dominating function on a graph $G$ is called the Roman domination number, denoted by ${\gamma }_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^{\prime }\subseteq E(G)$ for which ${\gamma }_R(G-E^{\prime })>{\gamma }_R(G)$. In this paper, we first show that the decision problem for determining $b_{\mathrm{R}}(G)$ is NP-hard even for bipartite graphs and then we establish some sharp bounds for $b_{\mathrm{R}}(G)$ and characterizes all graphs attaining some of these bounds.

15 pages, 35 references