|
چکیده
|
A Roman dominating function on a graph G = (V, E) is a function f : V −→ {0, 1, 2} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = P v∈V f(v). The Roman domination number of a graph G, denoted by γR(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sdγR (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that 1 ≤ sdγR (G) ≤ 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.
|