# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 3 Complexity and Enumeration in Special Graph Classes
### Cobipartite Graphs  
Now, we consider _cobipartite graphs_, which are the complementary graphs of bipartite graphs. These graphs can be also characterized as graphs for which the vertex set can be partitioned into two cliques. On this graph class, Perfect Roman Domination is solvable in polynomial time.  
Theorem 4.3: Perfect Roman Domination _is polynomial-time solvable on cobipartite graphs._  
Proof: Let \(G=(V,E)\) be a cobipartite graph, with \(V\) partitioned into the two cliques \(C_{1},C_{2}\subseteq V\). For \(v\in V\), define the perfect Roman dominating function  
\[g_{v}:V\to\{0,1,2\},x\mapsto\begin{cases}0,&x\in N(v)\,,\\ 1,&x\in V\setminus N[v]\,,\\ 2,&x=v\,.\end{cases}\]  
Let \(f\in\{0,1,2\}^{V}\) be a perfect Roman dominating function with \(|V_{2}(f)\cap C_{1}|\geq 2\) and \(v\in C_{2}\). Next, we prove that \(\omega(g_{v})\leq\omega(f)\). For each \(u\in C_{1}\setminus V_{2}(f)\), \(|V_{2}(f)\cap N(u)|\geq 2\)Hence, \(C_{1}\subseteq V_{1}(f)\cup V_{2}(f)\). Since \(C_{2}\subseteq N[v]=V_{0}(g_{v})\cup\{v\}\), \(\omega(g_{v})\leq|C_{1}|+2\leq\omega(f)\). Symmetrically, \(\omega(g_{v})\leq|C_{1}|+2\leq\omega(f)\) for \(v\in C_{1}\) and a perfect Roman dominating function \(f\) with \(|V_{2}(f)\cap C_{2}|\geq 2\).  
Let \(f\) be a minimum perfect Roman dominating function on \(G\). By the previous considerations, we can assume \(|V_{2}(f)\cap C_{i}|\leq 1\) for each \(i\in\{1,2\}\). This leaves only \(|V|^{2}+|V|\) many possibilities to check.  
As mentioned before, [PERSON] et al. [18] proved that Unique Response Roman Domination is NP-complete on bipartite graphs. For cobipartite graphs, this problem is polynomial-time solvable. For this result, we use the idea of 2-packings; we also refer to the discussion in [33]. Let \(G=(V,E)\) be a graph. A set \(S\subseteq V\) is called a _2-packing_ if the distance between two vertices in \(S\) is at least 3. [PERSON] et al. [34] presented a proof for \(u_{r}(G)=\min\{2|S|+|V(G)\setminus N_{G}[S]|\mid S\text{ is a 2-packing}\}\). Analogously to this, we can prove that, for each graph \(G=(V,E)\), there exists a bijection \(\psi_{G}\) between all 2-packings of the graph and all unique response Roman dominating functions. Here, for a 2-packing \(S\) and for \(x\in V\),  
\[\psi_{G}(S)(x)=\begin{cases}0,&x\in N(S)\setminus S\,,\\ 1,&x\in V\setminus N(S)\,,\\ 2,&x\in S\,.\end{cases}\]  
This also yields that, for each unique response Roman dominating function \(f\), \(V_{2}(f)\) is a 2-packing. This is the main idea of our algorithm.  
Lemma 2: Unique Response Roman Domination _is polynomial-time solvable on cobipartite graphs. Furthermore, there are at most \(\frac{|V|^{2}}{4}\) many 2-packings, or unique response Roman dominating functions, in \(G=(V,E)\)._  
Proof: Let \(G=(V,E)\) be a cobipartite graph, together with the partition into the two cliques \(C_{1},C_{2}\subseteq V\). Two vertices from the same clique cannot be in a 2-packing at the same time. Therefore, from each clique, there can be at most one vertex in a 2-packing. Hence, there are at most \(|C_{1}|\cdot|C_{2}|\) many 2-packings, or unique response Roman dominating functions. As \(C_{1},C_{2}\) is a partition of \(V\), this leads to \(|C_{1}|\cdot|C_{2}|=|C_{1}|\cdot|V\setminus C_{1}|=|C_{1}|\cdot(|V|-|C_{1}|)\) many 2-packings. This expression is maximal if \(|C_{1}|=|C_{2}|\), which implies that there are at most \(\frac{|V|^{2}}{4}\) many 2-packings, or unique response Roman dominating functions, in \(G\).  
As indicated in the proof, the upper bound \(\frac{|V|^{2}}{4}\) is tight: consider the complement of the complete bipartite graph \(K_{t,t}\), where both classes have the same size \(t\). This is interesting, as there could be exponentially many unique response Roman dominating functions even on connected split graphs, which is quite a related class of graphs that we consider next.