In his article “Defend the Roman Empire!” (1999), Ian Stewart discussed a strategy of Emperor Constantine for defending the Roman Empire. Motivated by this article, Cockayne et al. (2004) introduced the notion of Roman domination in graphs.
Let 𝐺 = (𝑉, 𝐸) be a graph. A Roman dominating function of 𝐺 is a function 𝑓 ∶ 𝑉 → {0, 1, 2} such that every vertex 𝑣 for which 𝑓(𝑣) = 0 has a neighbor 𝑢 with 𝑓(𝑢) = 2. The weight of a Roman dominating function 𝑓 is 𝑤(𝑓) =∑_𝑣∈𝑉 𝑓(𝑣). The Roman domination number of a graph 𝐺, denoted by 𝛾_𝑅(𝐺), is the minimum weight of all possible Roman dominating functions.
This paper introduces a quantity 𝑅(𝑥𝑦) for each pair of non-adjacent vertices {𝑥, 𝑦 }in 𝐺, called the Roman dominating index of{ 𝑥, 𝑦} , which is defined by &𝑅(𝑥𝑦) = 𝛾_𝑅(𝐺) − 𝛾_𝑅(𝐺 + 𝑥𝑦)&. We prove that 0 ≤ 𝑅(𝑥𝑦) ≤ 1 and give a necessary and sufficient condition on {𝑥, 𝑦} for which 𝑅(𝑥𝑦)= 1.
This paper also introduces the Roman-critical graph. We call 𝐺 = (𝑉, 𝐸) Roman-critical if 𝛾_𝑅(𝐺 − 𝑒) > 𝛾_𝑅(𝐺) , ∀𝑒 ∈ 𝐸 . It is proved that a Roman-critical graph can only be a star graph whose order is not equal to 2, or the union of such graphs.
In addition, this paper shows that for each connected graph 𝐺 of order& 𝑛 ≥ 3,2 ≤ 𝛾_𝑅(𝐺) ≤frac{4𝑛}{5}&. A family of graphs for which the respective equality holds is also provided.
Finally, this paper finds the lower bound of the Roman domination number for 3-regular graphs and the exact value of the Roman domination number for &𝐶_frac{𝑛}{2}*𝑃2& and 3-regular circulant graphs.