# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 3 Complexity and Enumeration in Special Graph Classes
### Remarks on Enumeration of Unique Response Roman Dominating Functions in Split Graphs  
Enumerating 2-packings (corresponding to unique response Roman dominating functions) in general graphs in time \(\mathcal{O}(1.5399^{n})\) was shown in [35]. Corollary 2: _All unique response Roman dominating functions of a connected split graph of order \(n\) can be enumerated in time \(\mathcal{O}(\sqrt[3]{3}^{n})\subseteq\mathcal{O}(1.4423^{n})\)._  
Proof: Non-trivial connected split graphs have no isolates. By Observation 3, we can hence use the enumeration algorithm for minimal Roman dominating functions on split graphs of order \(n\) from [29] which runs in time \(\mathcal{O}(\sqrt[3]{3}^{n})\). \(\Omega(\sqrt[3]{3}^{|V|})\) is even a tight lower bound for connected split graphs as shown next. **Theorem 11**. : _There is an infinite family of connected split graphs \(G_{t}=(V_{t},E_{t})\) with \(\Omega\big{(}\sqrt[3]{5}^{|V_{t}|}\big{)}\) many unique response Roman dominating functions._  
Proof. : We only need to consider the split graph family \(G_{t}=(V_{t},E_{t})\) with \(V_{t}\coloneqq C_{t}\cup I_{t}\), \(C_{t}\coloneqq\{c_{1},\ldots,c_{t}\}\), \(I_{t}\coloneqq\{v_{1},\ldots,v_{2t}\}\) and  
\[E_{t}\coloneqq\binom{C_{t}}{2}\cup\{\{c_{i},v_{2i-1}\},\{c_{i},v_{2i}\}\mid i \in\{1,\ldots,t\}\}.\]  
Clearly, \(|V_{t}|=3t\). By the arguments from Theorem 7, for each unique response Roman dominating function \(f\) on \(G_{t}\) with \(|V_{2}(f)\cap C_{t}|=1\), in fact \(|V_{2}(f)|=1\). There are \(t\) many such unique response Roman dominating functions. Let \(f\) be a unique response Roman dominating function with \(V_{2}(f)\cap C_{t}=\emptyset\). In this situation, for each \(i\in\{1,\ldots,t\}\), there are three ways to dominate \(c_{i}\):  
* \(f(c_{i})=f(v_{2i-1})=f(v_{2i})=1\);
* \(f(c_{i})=f(v_{2i})=0\) and \(f(v_{2i-1})=2\);
* \(f(c_{i})=f(v_{2i-1})=0\) and \(f(v_{2i})=2\). Hence, there are \(t+3^{t}=\frac{|V|}{3}+\sqrt[3]{5}^{|V|}\) many unique response Roman dominating functions. For general graphs, the best lower bound [35] is \(\mathcal{O}(1.4970^{n})\). It should be mentioned that the polynomial-delay property of the Roman dominating function-enumeration algorithm from [29] is not inherited for enumerating the unique response Roman dominating function, as each minimal Roman dominating function is not a unique response Roman dominating function. Nonetheless, we present a sketch of a direct polynomial-delay branching enumeration algorithm for enumerating unique response Roman dominating functions that is optimal due to Theorem 11. For this purpose, we consider each 2-packing on a connected split graph and use the bijesction between unique response Roman dominating functions and 2-packings. Our algorithm is a modification of the recursive backtracking algorithm of [36] and has polynomial delay with the same arguments. The algorithm of [36] is a general approach to enumerate all sets of \(\mathcal{F}\subseteq 2^{U}\) for a universe \(U\), where \(\mathcal{F}\) fulfills the following downward closure property: if \(X\in\mathcal{F}\) and \(Y\subseteq X\), then \(Y\in\mathcal{F}\). **Theorem 12**. : _All unique response Roman dominating functions of a connected split graph of order \(n\) can be enumerated in time \(\mathcal{O}(\sqrt[3]{5}^{n})\) with polynomial delay and polynomial space._  
One of the rather surprising aspects of the proof is that we do not need any sophisticated measure-and-conquer methodology to analyze the run-time of the branching algorithm by a simple case analysis concerning the vertex degrees. In the core part of the algorithm, we decide if a vertex in the independent set is put into the related 2-packing or not; also cf. [36] concerning polynomial delay. Proof. : Let \(G=(V,E)\) be a connected split graph with the partition \(V=C\cup I\), where \(C\) is a clique and \(I\) is an independent set. With the arguments from Theorem 7, we can first enumerate each of the \(|C|\) many 2-packings \(S\) with \(S\cap C\
eq\emptyset\).