Trees whose Roman domination subdivision number is 2
Abstract
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) = Σ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. The authors have recently proved that for any tree T of order at least 3, sdγR(T) ≤ 2. In this paper, we provide a constructive characterization of the trees whose Roman domination subdivision number is 2.
