# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 3 Complexity and Enumeration in Special Graph Classes
### Interval Graphs
Since \(V_{2}(f)\cap C=\emptyset\) would imply \(f=1\) (constant) and \(\omega(f)=|C|+|I|\), let us assume \(\{v\}=V_{2}(f)\cap C\). Therefore, \(C\cap V_{1}(f)=\emptyset\) holds. Hence, \(\omega(f)=2+|I\setminus N_{G}(v)|\). This implies \(u_{R}(G)\leq\min_{v\in C}(2+|I\setminus N_{G}(v)|)\leq 2+|I|\). Secondly, let us assume \(V_{2}(f)\subseteq I\). As \(I\) is an independent set and there is no vertex in \(C\) with the value \(2\), \(f(v)\geq 1\) for each \(v\in I\). This implies  
\[\omega(f)=|I|+|V_{2}(f)|+|C\setminus N_{G}(V_{2}(f))|\geq|I|+1\,.\]  
Equality holds if and only if there exists a vertex \(v\in I\) with \(N_{G}(v)=C\) and, for all \(u\in I\), \(f(u)=2\) if and only if \(u=v\). In this case, \(C\) is not maximal, contradicting our assumption. Thus, this second case can never give a smaller value than the first one, i.e., \(u_{R}(G)=\min_{v\in C}(2+|I\setminus N_{G}(v)|)\). Hence, in order to solve the Unique Response Roman Domination on \(G\), we only have to find the vertex with the highest degree, as it will be in a maximal clique. Interestingly, the seemingly very similar problem of Perfect Roman Domination on split graphs is harder to solve. To see this, we will use a problem called Perfect Code that is formally defined next. **Problem name:** Perfect Code (PC for short)  
**Given:** A graph \(G=(V,E)\) and \(k\in\mathbb{N}\)  
**Question:** Is there a perfect code \(D\) on \(G\) with \(|D|\leq k\)? It is known that Perfect Code is NP-complete, also in restricted graph classes like cubic planar graphs and if \(k\geq|V|\); see [24; 31; 32]. Theorem 8: Perfect Roman Domination _on split graphs is NP-complete._  
Proof: Membership follows from Perfect Roman Domination on general graphs. To prove NP-hardness, we will make use of the NP-hardness of Perfect Code. Let \(G=(V,E)\) be a graph and \(k\in\mathbb{N}\). To avoid trivialities, assume \(k\leq|V|\). Define \(t=3\cdot|V|+4\), \(k^{\prime}=k+|V|+4\) and \(G^{\prime}=(V^{\prime},E^{\prime})\) with  
\[V^{\prime}= \{x,y\}\cup\{v^{\prime}\mid v\in V\}\cup\{v_{i}\mid v\in V,i\in[ t]\}\cup\{a_{1},b_{1},\dots,a_{t},b_{t}\},\] \[E^{\prime}= \{\{x,a_{i}\},\{y,b_{i}\}\mid i\in[t]\}\cup\{\{v^{\prime},u_{i} \}\mid v,u\in V,u\in N[v],i\in[t]\}\cup\] \[\binom{\{x,y\}\cup\{v^{\prime}\mid v\in V\}}{2}.\]  
The instance \((G^{\prime},k^{\prime})\) of Perfect Roman Domination can be constructed in polynomial time. Moreover, \(G^{\prime}\) is easily seen to be a split graph. We still have to prove that \((G,k)\) is a yes-instance of Perfect Code if and only if \((G^{\prime},k^{\prime})\) is a yes-instance of Perfect Roman Domination. Let \(S\subseteq V\) be a perfect code of \(G\) with \(|S|\leq k\). Define \(f\in\{0,1,2\}^{V}\) by the sets  
Figure 3.0 Figure 3.1 Figure 3.2  
This implies \(\omega(f)=|V\setminus S|+4+2\cdot|S|=|V|+4+|S|\leq k^{\prime}\). The set \(\{a_{1},\dots,a_{t}\}\cup\{v^{\prime}\mid f(v)\
eq 2\}\) is only dominated by \(x\) and the vertices \(b_{1},\dots,b_{t}\) are only dominated by \(y\). Assume there are \(v\in V\) and \(i\in[t]\) such that \(|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|\
eq 1\). By \(N_{G^{\prime}}(v_{i})=\{u^{\prime}\mid u\in N_{G}[v]\}\), this implies \(|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|=|N_{G}(v)\cap S|\
eq 1\). This contradicts that \(S\) is a perfect code. Assume that \(f\in\{0,1,2\}^{V^{\prime}}\) is a minimum perfect Roman dominating function (so also minimal) with \(\omega(f)\leq k^{\prime}\). Claim 3: _For each \(z\in\{v_{i},a_{i},b_{i}\mid i\in[t],v\in V\}\), it holds that \(f(z)=0\)._  
Proof: For the sake of contradiction, assume that there is some \(v\in V\) and \(i\in[t]\) with \(f(v_{i})=2\). This implies with Theorem 1 that \(\{x,y\}\cup\{z^{\prime}\mid z\in V\}\subseteq N_{G^{\prime}}(u^{\prime})\) has no vertex with \(f\)-value \(2\). Thus, \(N_{G^{\prime}}(v_{i})\cap V_{2}(f)=\emptyset\). Therefore, \(f(v_{j})\
eq 0\) for each \(j\in[t]\). Hence, \(\omega(f)\geq t+1>k^{\prime}\), contradicting the choice of \(f\). Assume that there are some \(v\in V\) and \(i\in[t]\) with \(f(v_{i})=1\).