A Note on Roman Bondage Number of Graphs

Abstract

A Roman dominating function (or simply RDF) on a graph \(G = (V(G), E(G))\) is a labeling \(f: V(G) \to \{0, 1, 2\}\) satisfying the condition that every vertex with label \(0\) has at least a neighbor with label \(2\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum of \(\sum_{v \in V(G)} f(v)\) over such functions. The Roman bondage number, \(b_R(G)\), of a graph \(G\) with maximum degree at least two is the minimum cardinality among all sets \(E \subseteq E(G)\) for which \(\gamma_R(G – E) > \gamma_R(G)\). It was conjectured that if \(G\) is a graph of order \(n\) with maximum degree at least two, then \(b_R(G) \leq n – 1\). In this paper, we settle this conjecture. More precisely, we prove that for every connected graph of order \(n \geq 3\), \(b_R(G) \leq \min\{n – 1, n – \gamma_R(G) + 5\}\).