 |
Let f : V → {0, 1, 2} be a function on a graph G = (V, E). A vertex v with f (v) = 0 is said to
be undefended with respect to f if it is not adjacent to a vertex u with f (u) > 0. A function f is
called a weak Roman dominating function (WRDF) if each vertex v with f (v) = 0 is adjacent
to a vertex u with f (u) > 0, such that the function f 0 defined by f 0 (v) = 1, f 0 (u) = f (u) − 1,
and f 0 (w) = f (w) for all w ∈ V \ {v, u}, has no undefended vertex. The weight of a WRDF is
the sum of its function values over all vertices, and the weak Roman domination number γ r (G)
is the minimum weight of a WRDF in G. In this paper, we consider the effects of edge deletion
on the weak Roman domination number of a graph. We show that the deletion of an edge of
G can increase the weak Roman domination number by at most 1. Then we give a necessary
condition for γ r -ER-critical graphs, that is, graphs G whose weak Roman domination number
increases by the deletion of any edge. Restricted to the class of trees, we provide a constructive
characterization of all γ r -ER-critical trees.
- Other
