A Roman dominating function on a graph G = (V(G), E(G)) is a labelling f: (V(G) → {0, 1, 2} satisfying the condition that every vertex with label 0 has at least a neighbour with label 2. The Roman domination number γ_R(G) of G is the minimum of σ_(v∈V(G))f_((v)) over all such functions. The Roman bondage number b_R(G) of G is the minimum cardinality of all sets for which γ_R(G E) > γ_R(G). Recently, it was proved that for every planar graph P, b_R(P) ≤ Δ(P) + 6, where Δ(P) is the maximum degree of P. We show that the Roman bondage number of every planar graph does not exceed 15 and construct infinitely many planar graphs with Roman bondage number equal to 7.
展开▼
