In graph theory, a Roman dominating set (RDS) is a special type of dominating set inspired by historical military defense strategies of the Roman Empire. The concept models a scenario where cities (vertices) can be defended by legions stationed either within the city or in neighboring cities. A city is considered secure if it either has at least one legion stationed there, or if it has no legions but is adjacent to a city that has at least two legions, allowing one legion to be sent for defense while leaving the original city still protected. The Roman domination number of a graph measures the minimum total number of legions needed to protect all cities according to this strategy.
Definition Let G = ( V , E ) {\displaystyle G=(V,E)} be a graph. A Roman dominating function (RDF) is a function f : V → { 0 , 1 , 2 } {\displaystyle f:V\to \{0,1,2\}} such that for every vertex v {\displaystyle v} with f ( v ) = 0 {\displaystyle f(v)=0} , there exists a vertex u {\displaystyle u} adjacent to v {\displaystyle v} with f ( u ) = 2 {\displaystyle f(u)=2} . The weight of a Roman dominating function f {\displaystyle f} is w ( f ) = ∑ v ∈ V f ( v ) {\displaystyle w(f)=\sum _{v\in V}f(v)} . The Roman domination number γ R ( G ) {\displaystyle \gamma _{R}(G)} is the minimum weight among all Roman dominating functions for G {\displaystyle G} . Equivalently, let ( V 0 , V 1 , V 2 ) {\displaystyle (V_{0},V_{1},V_{2})} be an ordered partition of V {\displaystyle V} where V i = { v ∈ V : f ( v ) = i } {\displaystyle V_{i}=\{v\in V:f(v)=i\}} . Then f {\displaystyle f} is a Roman dominating function if and only if every vertex in V 0 {\displaystyle V_{0}} is adjacent to at least one vertex in V 2 {\displaystyle V_{2}} .
Examples For the complete graph K n {\displaystyle K_{n}} with n ≥ 2 {\displaystyle n\geq 2} , γ R ( K n ) = 2 {\displaystyle \gamma _{R}(K_{n})=2} , achieved by assigning 2 to any single vertex and 0 to all others. For the path graph P n {\displaystyle P_{n}} and cycle graph C n {\displaystyle C_{n}} , γ R ( P n ) = γ R ( C n ) = ⌈ 2 n / 3 ⌉ {\displaystyle \gamma _{R}(P_{n})=\gamma _{R}(C_{n})=\lceil 2n/3\rceil } . For the empty graph K ¯ n {\displaystyle {\overline {K}}_{n}} , γ R ( K ¯ n ) = n {\displaystyle \gamma _{R}({\overline {K}}_{n})=n} , since each vertex must be assigned at least 1. For the complete n-partite graph K m 1 , m 2 , … , m n {\displaystyle K_{m_{1},m_{2},\dots ,m_{n}}} with partition sizes m 1 ≤ m 2 ≤ ⋯ ≤ m n {\displaystyle m_{1}\leq m_{2}\leq \dots \leq m_{n}} :
… excerpt ends here. Continue reading the full article.
