# MathSciDoc: An Archive for Mathematician ∫

#### S.-T. Yau High School Science Awarded Papersmathscidoc:1608.35034

2009
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.
```@inproceedings{shizhi2009roman,