Roman dominating set

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

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

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

Examples

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

For the path graph $P_{n}$ and cycle graph $C_{n}$ , $γ_{R} (P_{n}) = γ_{R} (C_{n}) = ⌈ 2 n / 3 ⌉$ .

For the empty graph ${\overline{K}}_{n}$ , $γ_{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}, \dots, m_{n}}$ with partition sizes $m_{1} \leq m_{2} \leq \dots \leq m_{n}$ :

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

Basic properties

Several properties of Roman domination were established by Cockayne et al.:

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

A graph $G$ is called a Roman graph if $γ_{R} (G) = 2 γ (G)$ . This occurs if and only if $G$ has a Roman dominating function of minimum weight with $V_{1} = ∅︀$ .

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.

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

R_{G} (v) = \sum_{f \in F} f (v)

Some basic properties of Roman domination value are known:

$0 \leq R_{G} (v) \leq 2 τ_{R} (G)$ , where $τ_{R} (G)$ is the number of $γ_{R} (G)$ -functions
$\sum_{v \in V (G)} R_{G} (v) = τ_{R} (G) γ_{R} (G)$
If there is a graph isomorphism mapping vertex $v$ in $G$ to vertex $v^{'}$ in $G^{'}$ , then $R_{G} (v) = R_{G^{'}} (v^{'})$

Extremal problems

Several extremal results have been established for Roman domination numbers.

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

For any $n$ -vertex graph $G$ with $n \geq 3$ , $5 \leq γ_{R} (G) + γ_{R} (\overline{G}) \leq n + 3$ .

For any $n$ -vertex graph $G$ with $n \geq 160$ , $γ_{R} (G) γ_{R} (\overline{G}) \leq 16 n / 5$ .

If $G$ is a connected $n$ -vertex graph with $δ (G) \geq 2$ and $n \geq 9$ , then $γ_{R} (G) \leq 8 n / 11$ .

Algorithms and complexity

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

References

1 2 3 4 5 6 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
1 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
1 2 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
1 2 3 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

[cockayne2004-1] 1 2 3 4 5 6 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

[fu2009-2] 1 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

[pushpam2024-3] 1 2 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

[chambers2009-4] 1 2 3 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