# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 2 Enumerating Minimal Perfect Roman Domination
The definition of \(B^{-1}\) implies \(v\in V_{0}(B^{-1}(B(f)))\). Hence, \(B^{-1}(B(f))=f\). Assume \(v\in V_{0}(g)\). Theorem 1 implies \(|N_{G}(v)\cap V_{2}(f)|=1\). Therefore, \(v\in V_{0}(B(B^{-1}(f)))\cap V_{0}(B^{-1}(f))\). For \(v\in V_{1}(g)\) with \(N_{G}(v)\cap V_{2}(g)=\emptyset\), the construction of the functions \(B,B^{-1}\) implies \(v\in V_{1}(B(B^{-1}(f)))\cap V_{1}(B^{-1}(f))\). Let \(v\in V_{1}(g)\) with \(|N_{G}(v)\cap V_{2}(g)|\geq 2\). This leads to \(v\in V_{0}(B^{-1}(g))\) and \(v\in V_{1}(B(B^{-1}(g)))\). Hence, \(B(B^{-1}(g))=g\). Therefore, the theorem holds. This bijection is a so-called _parsimonious reduction_. This is a class of reductions designed for enumeration problems. For more information, we refer to [28]. Theorem 3.1 implies some further results thanks to [23]. Corollary 1: _There are graphs of order \(n\) that have at least \(\sqrt[5]{16}^{n}\in\Omega(1.7441^{n})\) many minimal perfect rdf._  
Theorem 3.2: _There is a polynomial-space, polynomial-delay algorithm that enumerates all minimal perfect Roman dominating functions of a given graph of order \(n\) in time \(\mathcal{O}^{*}(1.9332^{n})\)._  
Remark 3: It should be mentioned that the function \(B\) defined in the proof of Theorem 3.1 inherits inclusion-wise minimality, but this does not mean that, if \(f\) is a minimum Roman Dominating Function, then \(B(f)\) is a minimum perfect Roman dominating function. To see this, we consider the graph \(G=(V,E)\) with \(V\coloneqq\{v_{1},\ldots,v_{8}\}\) and  
\[E\coloneqq \{\{v_{i},w_{i}\},\{\overline{v_{i}},w_{i}\},\{v_{i},y_{i}\},\{ \overline{v_{i}},y_{i}\},\{z_{i},y_{i}\}\ |\ i\in[n]\}\cup\]6  
The graph is visualized in \[E\coloneqq \{\{v_{i},w_{i}\},\{\overline{v_{i}},w_{i}\},\{v_{i},y_{i}\},\{ \overline{v_{i}},y_{i}\},\{z_{i},y_{i}\}\ |\ i\in[n]\}\cup\]7 Since \(v_{1},v_{2}\) and \(v_{7},v_{8}\) are pairs of false twins and \(v_{1},v_{7}\) have no common neighbors, for each Roman dominating function \(f\) on \(G\), \(\omega(f)\geq 4\). Therefore, \(f\in\{0,1,2\}^{V}\) with \(V_{0}(f)=\{v_{1},v_{2},v_{4},v_{5},v_{7},v_{8}\}\), \(V_{1}(f)=\emptyset\), and \(V_{2}(f)=\{v_{3},v_{6}\}\) is a minimum Roman dominating function. \(B(f)\) is given by \(V_{0}(B(f))=\{v_{1},v_{2},v_{7},v_{8}\}\), \(V_{1}(B(f))=\{v_{4},v_{5}\}\), and \(V_{2}(f)=\{v_{3},v_{6}\}\). The weight is \(\omega(B(f))=6\). The minimal perfect Roman dominating function \(g\in\{0,1,2\}\) with \(V_{0}(g)=\{v_{1},v_{2},v_{4},v_{5}\}\), \(V_{1}(g)=\{v_{6},v_{7},v_{8}\}\) and \(V_{2}(g)=\{v_{3}\}\) fulfills \(\omega(g)=5\). Hence, \(B(f)\) is no minimum perfect Roman dominating function. Let \(h\in\{0,1,2\}^{V}\) be a minimal perfect Roman dominating function. For \(h(v_{3})=h(v_{6})=2\), \(h=B(f)\), as \(v_{1},v_{2},v_{7},v_{8}\in N(V_{2}(h))\) are pendant. Assume \(h(v_{3})=2\
eq h(v_{6})\). If \(h(v_{4})=2\) (respectively, \(h(v_{5})=2\)), \(h(v_{7})=h(v_{8})=1\) and \(\omega(h)\geq 6\). For \(h(v_{7})=2\) (respectively, \(h(v_{8})=2\)), \(h(v_{8})=1\) (respectively, \(h(v_{7})=1\)) and \(\omega(g)=5\geq\omega(h)\). As \(v_{1},v_{2}\
otin V_{2}(h)\)for \(h(v_{3})=2\), the remaining possibility is \(h=g\). Thus, \(\omega(g)=5\leq\omega(h)\) holds for each minimal perfect Roman dominating function with \(h(v_{3})=2\
eq h(v_{6})\). Analogously, for perfect Roman dominating functions \(h\) with \(h(v_{6})\
eq 2=h(v_{3})\), \(\omega(g)=5\leq\omega(h)\). Let \(h(v_{3})\
eq 2\) and \(h(v_{6})\
eq 2\). Since \(N(v_{i})\subseteq\{v_{3},v_{6}\}\) for \(i\in\{1,2,4,5,7,8\}\), \(v_{1},v_{2},v_{4},v_{5},v_{7},v_{8}\
otin V_{0}(h)\). Hence, \(\omega(h)\geq 6\) and \(g\) is a minimum perfect Roman dominating function. Furthermore, \(B^{-1}(g)=g\) is not a minimum Roman dominating function. According to [29], we obtain some further results for special graph classes: Let \(G=(V,E)\), with \(n\coloneqq|V|\) being of the order of \(G\). If \(G\) is a forest or interval graph, then there is a perfect Roman dominating function enumeration algorithm that runs in time \(\mathcal{O}^{*}(\sqrt{3}^{n})\) with polynomial delay.