|
چکیده
|
Let G = (V;E) be a simple graph with vertex set V = V (G) and edge set E = E(G). A Roman dominating function (RDF) on a graph G is a function f : V ! {0; 1; 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v such that f(v) = 2. The weight of f is !(f) = v2V f(v). The minimum weight of an RDF on G, R(G), is called the Roman domination number of G. It is a fact that R(G) 2 (G) where (G) denotes the domination number of G. A graph G is called a Roman graph whenever R(G) = 2 (G). On the other hand, the differential of X is defined as @(X) = jB(X)j jXj and the differential of a graph G, written @(G), is equal to maxf@(X) : X V g. By using differential we provide a sufficient and necessary condition for the graphs to be Roman. We also modify the proof of a result on Roman trees. Finally we characterize the large family of trees T such that @(T) = n (T) 2.
|