A Roman dominating function (RDF) on a graph G is a labelling f : V(G) → {0, 1,2} such that every vertex with label 0 has a neighbor with label 2. A vertex u with f(u) = 0 is said to be undefended with respect to f if it is not adjacent to a vertex v with the positive weight. A function f : V(G) → {0,1,2} is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f' : V(G) → {0,1,2} defined by f'(u) = 1, f'(v) = f(v) - 1 and f'(w) = f(w) if w ∈ V - {u,v}, has no undefended vertex. The Roman bondage number bn(G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E' ⊆ E(G) for which γ_R(G - E') > γ_R(G). We extend this concept to a weak Roman dominating function as follows: The weak Roman bondage number b_r(G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E' ⊆ E(G) for which γ_r(G - E') > γ_r(G). In this paper we determine the exact values of the weak Roman bondage number for paths, cycles and complete bipartite graphs. We obtain bounds for trees and unicyclic graphs and characterize the extremal graphs.
展开▼
