Roman dominating set

An assignment of the weights 0, 1 or 2 to each vertex such that each vertex with weight 0 is adjacent to at least one vertex of weight 2 is called a Roman dominating function.

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 ${\displaystyle G=(V,E)}$ be a graph. A Roman dominating function (RDF) is a function ${\displaystyle f:V\to \{0,1,2\}}$ such that for every vertex ${\displaystyle v}$ with ${\displaystyle f(v)=0}$, there exists a vertex ${\displaystyle u}$ adjacent to ${\displaystyle v}$ with ${\displaystyle f(u)=2}$.^[1]

The weight of a Roman dominating function ${\displaystyle f}$ is ${\displaystyle w(f)=\sum _{v\in V}f(v)}$. The Roman domination number ${\displaystyle \gamma _{R}(G)}$ is the minimum weight among all Roman dominating functions for ${\displaystyle G}$.

Equivalently, let ${\displaystyle (V_{0},V_{1},V_{2})}$ be an ordered partition of ${\displaystyle V}$ where ${\displaystyle V_{i}=\{v\in V:f(v)=i\}}$. Then ${\displaystyle f}$ is a Roman dominating function if and only if every vertex in ${\displaystyle V_{0}}$ is adjacent to at least one vertex in ${\displaystyle V_{2}}$.^[1]

Examples

For the complete graph ${\displaystyle K_{n}}$ with ${\displaystyle n\geq 2}$, ${\displaystyle \gamma _{R}(K_{n})=2}$, achieved by assigning 2 to any single vertex and 0 to all others.

For the path graph ${\displaystyle P_{n}}$ and cycle graph ${\displaystyle C_{n}}$, ${\displaystyle \gamma _{R}(P_{n})=\gamma _{R}(C_{n})=\lceil 2n/3\rceil }$.^[1]

For the empty graph ${\displaystyle {\overline {K}}_{n}}$, ${\displaystyle \gamma _{R}({\overline {K}}_{n})=n}$, since each vertex must be assigned at least 1.

For the complete n-partite graph ${\displaystyle K_{m_{1},m_{2},\dots ,m_{n}}}$ with partition sizes ${\displaystyle m_{1}\leq m_{2}\leq \dots \leq m_{n}}$:^[1]

• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=2}$ if ${\displaystyle m_{1}=1}$.
• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=3}$ if ${\displaystyle m_{1}=2}$.
• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=4}$ if ${\displaystyle m_{1}\geq 3}$.

Basic properties

Several properties of Roman domination were established by Cockayne et al.:^[1]

• For any graph ${\displaystyle G}$, ${\displaystyle \gamma (G)\leq \gamma _{R}(G)\leq 2\gamma (G)}$, where ${\displaystyle \gamma (G)}$ is the domination number.
• ${\displaystyle \gamma (G)=\gamma _{R}(G)}$ if and only if ${\displaystyle G}$ is the empty graph.
• If ${\displaystyle G}$ has a vertex of degree ${\displaystyle n-1}$, then ${\displaystyle \gamma _{R}(G)=2}$.
• For any Roman dominating function ${\displaystyle f=(V_{0},V_{1},V_{2})}$:
  • The subgraph induced by ${\displaystyle V_{1}}$ has maximum degree at most 1.
  • No edge joins ${\displaystyle V_{1}}$ and ${\displaystyle V_{2}}$.
  • Each vertex in ${\displaystyle V_{0}}$ is adjacent to at most two vertices in ${\displaystyle V_{1}}$.
  • ${\displaystyle V_{2}}$ is a dominating set for the subgraph induced by ${\displaystyle V_{0}\cup V_{2}}$.

A graph ${\displaystyle G}$ is called a Roman graph if ${\displaystyle \gamma _{R}(G)=2\gamma (G)}$.^[2] This occurs if and only if ${\displaystyle G}$ has a Roman dominating function of minimum weight with ${\displaystyle V_{1}=\emptyset }$.

Roman domination value

The Roman domination value of a vertex extends the concept of Roman domination by considering how many minimum Roman dominating functions assign positive values to that vertex.^[3]

For a graph ${\displaystyle G}$, let ${\displaystyle F}$ be the set of all ${\displaystyle \gamma _{R}(G)}$-functions (Roman dominating functions of minimum weight). For a vertex ${\displaystyle v\in V}$, the Roman domination value ${\displaystyle R_{G}(v)}$ is defined as:

${\displaystyle R_{G}(v)=\sum _{f\in F}f(v)}$

Some basic properties of Roman domination value are known:^[3]

• ${\displaystyle 0\leq R_{G}(v)\leq 2\tau _{R}(G)}$, where ${\displaystyle \tau _{R}(G)}$ is the number of ${\displaystyle \gamma _{R}(G)}$-functions
• ${\displaystyle \sum _{v\in V(G)}R_{G}(v)=\tau _{R}(G)\gamma _{R}(G)}$
• If there is a graph isomorphism mapping vertex ${\displaystyle v}$ in ${\displaystyle G}$ to vertex ${\displaystyle v'}$ in ${\displaystyle G'}$, then ${\displaystyle R_{G}(v)=R_{G'}(v')}$

Extremal problems

Several extremal results have been established for Roman domination numbers.

For any connected ${\displaystyle n}$-vertex graph ${\displaystyle G}$ with ${\displaystyle n\geq 3}$, ${\displaystyle \gamma _{R}(G)\leq 4n/5}$.^[4] Equality holds if and only if ${\displaystyle G}$ is ${\displaystyle C_{5}}$ or obtained from ${\displaystyle n/5}$ copies of ${\displaystyle P_{5}}$ by adding a connected subgraph on the set of centers.

For any ${\displaystyle n}$-vertex graph ${\displaystyle G}$ with ${\displaystyle n\geq 3}$, ${\displaystyle 5\leq \gamma _{R}(G)+\gamma _{R}({\overline {G}})\leq n+3}$.^[4]

For any ${\displaystyle n}$-vertex graph ${\displaystyle G}$ with ${\displaystyle n\geq 160}$, ${\displaystyle \gamma _{R}(G)\gamma _{R}({\overline {G}})\leq 16n/5}$.^[4]

If ${\displaystyle G}$ is a connected ${\displaystyle n}$-vertex graph with ${\displaystyle \delta (G)\geq 2}$ and ${\displaystyle n\geq 9}$, then ${\displaystyle \gamma _{R}(G)\leq 8n/11}$.^[4]

Algorithms and complexity

The decision problem for Roman domination is NP-complete, even when restricted to bipartite, chordal, or planar graphs.^[1] However, polynomial-time algorithms exist for computing the Roman domination number on interval graphs, cographs, and strongly chordal graphs.^[2]

See also

• Dominating set
• Graph labeling

References

1. Cockayne, E. J.; Dreyer, P. A.; Hedetniemi, S. M.; Hedetniemi, S. T. (2004), "Roman domination in graphs", Discrete Mathematics, 278 (1–3): 11–22, doi:10.1016/j.disc.2003.06.004
2. Fu, Xueliang; Yang, Yuansheng; Jiang, Baoqi (2009), "Roman domination in regular graphs", Discrete Mathematics, 309 (6): 1528–1537, doi:10.1016/j.disc.2008.03.006
3. Pushpam, P. R. L.; Sampath, P. (2024), "Roman domination value in graphs" (PDF), Communications in Combinatorics and Optimization, doi:10.22049/cco.2024.28899.1769
4. Chambers, E. W.; Kinnersley, W.; Prince, N.; West, D. B. (2009), "Extremal problems for Roman domination", SIAM Journal on Discrete Mathematics, 23 (3): 1575–1586, doi:10.1137/070699688