Roman dominating set

Short description: Type of dominating set in graph theory

File:Roman domination.svg

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 $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 ${\gamma }_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\ge 2$, ${\gamma }_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$, ${\gamma }_R(P_n)={\gamma }_R(C_n)=\lceil 2n/3\rceil$.

For the empty graph ${\bar{K}}_n$, ${\gamma }_R({\bar{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\le m_2\le \dots \le m_n$:

• ${\gamma }_R(K_{m_1,\dots ,m_n})=2$ if $m_1=1$.
• ${\gamma }_R(K_{m_1,\dots ,m_n})=3$ if $m_1=2$.
• ${\gamma }_R(K_{m_1,\dots ,m_n})=4$ if $m_1\ge 3$.

Basic properties

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

• For any graph $G$, $\gamma (G)\le {\gamma }_R(G)\le 2\gamma (G)$, where $\gamma (G)$ is the domination number.
• $\gamma (G)={\gamma }_R(G)$ if and only if $G$ is the empty graph.
• If $G$ has a vertex of degree $n-1$, then ${\gamma }_R(G)=2$.
• For any Roman dominating function $f=(V_0,V_1,V_2)$:
  • 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 ${\gamma }_R(G)=2\gamma (G)$. This occurs if and only if $G$ has a Roman dominating function of minimum weight with $V_1=\mathrm{\varnothing }$.

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 ${\gamma }_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\le R_G(v)\le 2{\tau }_R(G)$, where ${\tau }_R(G)$ is the number of ${\gamma }_R(G)$-functions
• $\sum _{v\in V(G)}{R}_G(v)={\tau }_R(G){\gamma }_R(G)$
• If there is a graph isomorphism mapping vertex $v$ in $G$ to vertex $v^{\prime }$ in $G^{\prime }$, then $R_G(v)=R_{G^{\prime }}(v^{\prime })$

Extremal problems

Several extremal results have been established for Roman domination numbers.

For any connected $n$-vertex graph $G$ with $n\ge 3$, ${\gamma }_R(G)\le 4n/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\ge 3$, $5\le {\gamma }_R(G)+{\gamma }_R(\bar{G})\le n+3$.

For any $n$-vertex graph $G$ with $n\ge 160$, ${\gamma }_R(G){\gamma }_R(\bar{G})\le 16n/5$.

If $G$ is a connected $n$-vertex graph with $\delta (G)\ge 2$ and $n\ge 9$, then ${\gamma }_R(G)\le 8n/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.

See also

• Dominating set
• Graph labeling