# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 3 Complexity and Enumeration in Special Graph Classes
### Interval Graphs
Define  
\[f_{w,u,v}:=f^{\prime}_{w,u}+(2-\chi_{N(u)\cap N(w)})\cdot\chi_{\{v\}}+\chi_{ Y_{w,u,v}}\,.\]  
Clearly, \(\omega(f_{w,u,v})=\gamma_{w,u}+2-|\{v\}\cap N(u)\cap N(w)|+|Y_{w,u,v}|\) and \(f_{w,u,v}(x)=f^{\prime}_{w,u}(x)\in\{0,1,2\}\) for \(x\in V\setminus(\{v\}\cup Y_{w,u,v})\). In particular, \(f_{w,u,v}(u)=f^{\prime}_{w,u}(u)=2\). (More generally, \(V_{2}(f_{w,u,v})\supseteq V_{2}(f^{\prime}_{w,u})\).) Now we consider \(x\in Y_{w,u,v}\). For \(x\in L_{v}\setminus(L_{u}\cup N(v))\subseteq V\setminus L_{u}\), \(f^{\prime}_{w,u}(x)=0\). Otherwise, \(f^{\prime}_{w,u}-\chi_{\{x\}}\) would belong to \(\Gamma_{w,u}\) with \(\omega\left(f^{\prime}_{w,u}-\chi_{\{x\}}\right)<\omega\left(f^{\prime}_{w,u}\right)\). So assume \(x\in(N(v)\cup N(u))\setminus N(w)\). Since \(w\in P_{u}\), \(r_{w}<l_{x}<r_{u}<r_{v}\). If \(\emptyset\
eq(V_{2}(f^{\prime}_{w,u})\setminus\{u\})\cap N(x)\), this would contradict the fact that \(f^{\prime}_{w,u}(z)\
eq 2\) for all \(z\in W_{w}\setminus\{u\}\). Hence, \(f^{\prime}_{w,u}(z)=0\) because of minimality. Hence, \(Y_{w,u,v}\subseteq V_{0}(f^{\prime}_{w,u})\) and \(f_{w,u,v}(x)\in\{0,1,2\}\) for \(x\in Y_{w,u,v}\). Now consider \(f_{w,u,v}(v)\). As \(f^{\prime}_{w,u}(v)\
eq 2\), \(v\
otin Y_{w,u,v}\) and \(f^{\prime}_{w,u}(v)+1\leq f_{w,u,v}(v)\leq f^{\prime}_{w,u}(v)+2\), i.e., \(1\leq f_{w,u,v}(v)\leq 3\). We will next show that \(1\leq f_{w,u,v}(v)\leq 2\). For the sake of contradiction, assume \(f_{w,u,v}(v)=3\). Then, \(f^{\prime}_{w,u}(v)=1\) and \(v\
otin N(u)\cap N(w)\). As (in addition) \(r_{w}<r_{u}<r_{v}\) and \(l_{w}\leq l_{u}\leq l_{v}\), we must have \(r_{w}<l_{v}\). Hence, \(\{w,v\}\
otin E\). Figure 3: Examples illustrating our notions. nation belong on split graphs as explicitly asked in [19]. We will answer this question in a somewhat surprising manner: while Unique Response Roman Domination can be solved in linear time, Perfect Roman Domination turns out to be NP-complete. First, we will consider unique response Roman dominating functions on split graphs and prove a combinatorial result. Lemma 1: _Let \(G=(V,E)\) be a connected split graph with a clique \(C\) and an independent set \(I\) such that \(V=C\cup I\) and \(C\cap I=\emptyset\). For each unique response Roman dominating function \(f:V\rightarrow\{0,1,2\}\), one of the following conditions holds:_  
1. \(V_{2}(f)\cap I=\emptyset\) _and_ \(|V_{2}(f)\cap C|\leq 1\)_;_
2. \(V_{2}(f)\subseteq I\)_._  
Proof: Suppose that \(V_{2}(f)\
subseteq I\). By the definition of unique response Roman dominating function, two vertices of \(C\) cannot have the value \(2\) since \(C\) is a clique. Hence, \(|V_{2}(f)\cap C|\leq 1\). For the sake of contradiction, assume there are \(v\in I\) and \(u\in C\) with \(f(u)=f(v)=2\). As the function \(f\) is a unique response Roman dominating function, \(u\) and \(v\) cannot be neighbors. Since \(G\) is connected, \(\emptyset\subsetneq N_{G}(v)\subseteq C\setminus\{u\}\subseteq N_{G}(u)\). This contradicts the assumption that \(f\) is a unique response Roman dominating function. This lemma implies that we can solve Unique Response Roman Domination by looking for a vertex \(v\) of maximum degree (which must be in an inclusion-wise maximal clique) and setting the value of \(v\) to two and the values of the other vertices accordingly. This implies the following. Theorem 7: Unique Response Roman Domination _can be solved in linear time on split graphs._  
Proof: How can we find a unique response Roman dominating function of the smallest weight? Let us take a look at the unique response Roman dominating function for the two cases of Lemma 1. Without loss of generality, we can assume that for the given split graph \(G=(V,E)\), we have a decomposition \(V=C\cup I\) into a clique \(C\) and an independent set \(I\) such that \(C\) is inclusion-wise maximal. Consider the unique response Roman dominating function \(f:V\rightarrow\{0,1,2\}\). First, assume \(f\) fulfills \(V_{2}(f)\cap I=\emptyset\) and \(|V_{2}(f)\cap C|\leq 1\).