On the Roman \(k\)-bondage number of a graph (Q656138)

Given a positive integer \(k\) and a graph \(G\), a \textit{Roman \(k\)-dominating function} on \(G\) is a function \(f\) from the vertex set \(V(G)\) of \(G\) to \(\{0,1,2\}\) such that every vertex \(v \in V(G)\) with \(f(v) = 0\) has at least \(k\) neighbours \(u\) in \(G\) with\(f(u) = 2\). The concept of Roman \(1\)-dominating functions was introduced implicitly by \textit{I. Stewart} [``Defend the Roman Empire!,'' Sci. Amer. 281, 136--139 (1999)] and, independently, by \textit{C.S. ReVelle} and \textit{K.E. Rosing} [``Defendens imperium romanum: A classical problem in military strategy,'' Am. Math. Mon. 107, No.\,7, 585--594 (2000; Zbl 1039.90038)], and generalized to Roman \(k\)-dominating functions by \textit{K. Kämmerling} and \textit{L. Volkmann} [``Roman \(k\)-domination in graphs,'' J. Korean Math. Soc. 46, No.\,6, 1309--1318 (2009; Zbl 1177.05084)]. The \textit{weight of a Roman \(k\)-dominating function} of a graph \(G\) is the value \(\sum_{v \in V(G)} f(v)\). The minimum weight of a Roman \(k\)-dominating function on a graph \(G\) is called the \textit{Roman \(k\)-domination number}, and it is denoted \(\gamma_{kR}(G)\). The \textit{Roman \(k\)-bondage number \(b_{kR}\)} of a graph \(G\) with maximum degree at least two is the minimum cardinality of all sets \(E' \subset E(G)\) with \(\gamma_{kR}(G - E') > \gamma_{kR}(G)\). The concept of the Roman \(1\)-bondage number was introduced by \textit{N.J. Rad} and \textit{L. Volkmann} [``Roman bondage in graphs,'' Discuss. Math. Graph Theory, 31, No. 4, 763--773 (2011)]. The paper contains upper bounds on Roman \(k\)-bondage number, including the case \(k=1\). For instance, it is proved that if \(G\) is a connected graph of order \(n\) at least \(4\) with \(\gamma_R(G) \geq 3\), then the Roman \(1\)-bondage number of \(G\) is at most \((\gamma_R(G) - 2)\Delta(G) + 1\), where \(\Delta(G)\) denotes the maximum degree of \(G\). The graphs with Roman \(k\)-bondage number equal to \(1\) or \(2\) are characterised. (The characterisation in the case of \(k=2\) is somewhat technical.) Finally, the Roman \(k\)-bondage number is calculated for certain types of complete graphs and complete bipartite graphs.