# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 3 Complexity and Enumeration in Special Graph Classes
### Interval Graphs
Furthermore, we can assume \(|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|\
eq 1\), by Theorem 1. As by construction \(N_{G^{\prime}}(v_{i})=N_{G^{\prime}}(v_{j})\) for each \(j\in[t]\), we find \(|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|=|N_{G^{\prime}}(v_{j})\cap V_{2}(f)|\). If \(|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|=0\), then \(f(v_{j})\
eq 0\) holds for each \(j\in[t]\) since \(v_{j}\) is not dominated. Hence, \(\omega(f)\geq t\cdot|V|\geq t>k^{\prime}\), contradicting the choice of \(f\). Assume \(|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|\geq 2\). Thus, for each \(j\in[t]\), \(f(v_{j})\
eq 0\), as, otherwise, \(f\) is not perfect. This contradicts the construction as above. We can discuss the claims concerning \(a_{i}\) and \(b_{i}\) along very similar lines. Further, we know \(f(x)=f(y)=2\). Define \(S=\{v\mid f(v^{\prime})=2\}\). As \(f(v_{i})=0\) for each \(v\in V,i\in[t]\), \(|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|=1\). This implies that \(|N_{G}[v]\cap S|=1\) for each \(v\in V\). Therefore, \(S\) is a perfect code. Since \(f(x)=f(y)=2\), \(f(v^{\prime})\geq 1\) for all \(v\in V\). This implies that \(\omega(f)=|V|+|V_{2}(f)|+4=|V|+|S|+4\leq k^{\prime}\). Hence, \(|S|\leq k^{\prime}-4-|V|=k\). This concludes the proof of Theorem 3. We contrast this by giving a branching algorithm for Perfect Roman Domination that yields the following result. Our algorithm relies on combinatorial insights from Theorem 4 and [29], where Roman dominating functions have been discussed on split graphs so that \(V_{2}(f^{\prime})\cap I=\emptyset\) or \(V_{2}(f^{\prime})\cap C=\emptyset\) for minimum \(f^{\prime}\). Theorem 4.2: \(\omega(f)\)_-Perfect Roman Domination can be solved in time \(\mathcal{O}^{*}(\varphi^{\omega(f)})\) on split graphs, where \(\varphi\) is the golden ratio._  
Proof: Let \(G=(V,E)\) be a split graph with the vertex set partition \(V=C\cup I\), where \(C\) is a clique and \(I\) an independent set. Let \(k\) be the input parameter. Further, let \(f^{\prime}:V\to\{0,1,2\}\) be a minimum perfect Roman dominating function on \(G\). Then, by Theorem 4 and [29], where Roman dominating functions have been discussed on split graphs, \(V_{2}(f^{\prime})\cap I=\emptyset\) or \(V_{2}(f^{\prime})\cap C=\emptyset\). We have to consider these two possibilities for the perfect Roman dominating functions \(f\) that we will consider in our algorithm. For \(V_{2}(f)\cap C=\emptyset\), we just branch on each vertex in \(I\) if it obtains the value \(1\) or \(2\). The vertices cannot obtain the value \(0\), as they cannot be dominated by any other vertex. After deciding this, we can delete the vertex, and the parameter goes down by either \(1\) or \(2\). This gives us the branching vector \((1,2)\). When we have branched on each vertex in \(I\), then we assign \(0\) to each \(c\in C\) with \(|V_{2}(f)\cap N(c)|=1\), and we assign \(1\) otherwise (this is important to obtain the perfect Roman dominating function property). Now, we only need to check if any \(\omega(f)\) is at most the given parameter value \(k\). Now, we consider the perfect Roman dominating functions \(f\in\{0,1,2\}^{V}\) with \(V_{2}(f)\cap I=\emptyset\). As \(C\) is a clique, if \(|V_{2}(f)\cap C|\geq 2\), then \(C\subseteq V_{1}(f)\cup V_{2}(f)\). First, we consider the polynomially many perfect Roman dominating functions with \(|V_{2}(f)\cap C|=1\). Since these functions are unique response Roman dominating functions, this can be performed in polynomial time. After this, we guess two vertices from \(C\) and assign the value \(2\) to these vertices. Again, there are polynomially many possibilities here. From now on, we can branch on the remaining vertices in \(C\) and decide if these will be assigned to \(1\) or \(2\). Analogously to \(V_{2}(f)\cap C=\emptyset\), then we assign \(0\) to each \(v\in I\) with \(|V_{2}(f)\cap N(v)|=1\), and we assign \(1\) otherwise. Again, we also have to check if \(\omega(f)\) is at most the given parameter value \(k\).