Asian Journal of Mathematics and Computer Research

Abstract

A set S of vertices is a dominating set if every vertex in V \ S has a neighbour in S. A Roman dominating function (RDF) on a graph G = (V,E) is defined to be 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 for which f(v) = 2. A Roman dominating function f of G can also be represented by a set of ordered pairs S_f = {(v, f(v)) : v ∈ V } . A subset T of S_f is called a forcing subset of S_f if S_f is the unique extension of T to a γR(G)-function. We define a forcing Roman domination number of S_f denoted by F(S_f, γR), as F(S_f, R) = min{|T| : T is aforcing subset of S_f }. The forcing Roman domination number F(G, γR) of G is degined as F(G; γR) = min{f(S_f, γR) : f is a γR(G) function}. Hence for every graph G, F(G,γR) ≥ 0. In this paper, we initiate a study of this parameter. We also obtain the forcing Roman domination number of paths, cycles, complete graphs, and complete multipartite

graph.