The concept of Roman domination has recently been studied concerning enumerating and counting (WG 2022). It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, contrasting what is known about minimal dominating sets. The running time of the algorithm could be estimated as $\mathcal{O}(1.9332^n)$ on general graphs of order $n$. In this paper, we focus on special graph classes. More specifically, for chordal graphs, we present an enumeration algorithm running in time $\mathcal{O}(1.8940^n)$. For interval graphs, we can lower this time further to $\mathcal{O}(1.7321^n)$. Interestingly, this also matches (exactly) the known lower bound. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely $\mathcal{O}(\sqrt{3}^n)$. Furthermore, we show an enumeration algorithm running in time $\mathcal{O}(1.4656^n)$ for split graphs and for cobipartite graphs. Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on special graph families like paths.

翻译：最近对罗马统治的概念进行了有关计算和计数(WG 2022)的研究。 已经显示, 最小的罗马主宰功能可以用多元延迟来罗列, 比较了已知的最小支配数据集。 算法运行时间可以估算为$\ mathcal{ O} (1. 9332 ⁇ n) 。 在本文中, 我们的焦点是特殊的图表类别。 更具体地说, 对于 chordal 图形, 我们给出了一种按时间运行的查点算法 $\ mathcal{ O} (1. 8940 ⁇ n) $。 对于间距图, 我们可以将这一时间进一步降为$\ mathcal{ O} (1. 7321 ⁇ n) 。 有趣的是, 算法的运行时间也可以( ) 与已知的较低约束值相匹配 。 我们还可以提供一种更低和上等的森林边框, 也就是 $mathcal{ O} (\ qr) 等值。 此外, 我们展示了一种按时间运行的计算算算算算法, $mathal_ 和 coal_ sqolations sqollations