FORCING ROMAN DOMINATION IN GRAPHS
P. ROUSHINI LEELY PUSHPAM *
Department of Mathematics, D. B. Jain College, Chennai 600 097, Tamil Nadu, India
S. PADMAPRIEA
Department of Mathematics, Sri Sairam Engineering College, Chennai 600 044, Tamil Nadu, India
*Author to whom correspondence should be addressed.
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 Sf = {(v, f(v)) : v ∈ V } . A subset T of Sf is called a forcing subset of Sf if Sf is the unique extension of T to a γR(G)-function. We define a forcing Roman domination number of Sf denoted by F(Sf, γR), as F(Sf, R) = min{|T| : T is aforcing subset of Sf }. The forcing Roman domination number F(G, γR) of G is degined as F(G; γR) = min{f(Sf, γ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.
Keywords: Roman domination, forcing domination