Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes

NEW

Problem: The quoted “open problem” is not a single precise conjecture. I formalize its upper-bound half as:

For finite simple chordal graphs $G$ on $n$ vertices, can all minimal Roman dominating functions $f:V(G)\to\{0,1,2\}$ be enumerated in $O^*(c^n)$ time for some $c<1.8940$?

Here $f$ is Roman dominating if every vertex with value $0$ has a neighbor with value $2$, and minimal means no distinct Roman dominating $g\le f$ exists pointwise.

Result: Yes. The existing chordal branching algorithm already yields the sharper bound

$$O^*(1.89394^n),$$

hence strictly improves the stated $O^*(1.8940^n)$ bound.

Use the measure from Abu-Khzam–Fernau–Mann:

$$\mu=|A|+0.710134|\overline{V_1}|+0.434799|\overline{V_2}|.$$

For $c=1.89394$, every branching vector $(a_i)$ in their chordal analysis satisfies

$$\sum_i c^{-a_i}\le 1.$$

The tight vectors give:

$$\begin{aligned} (0.565201,1.869598)&:\quad 0.99999514<1,\\ (0.710134,1.579732)&:\quad 0.99999494<1. \end{aligned}$$

All other listed chordal branch vectors have smaller sums, at most $0.975784$. Thus the search tree has size $O(c^\mu)$, and initially $\mu=n$. Since the cited branching rules are exhaustive for chordal graphs and preserve polynomial delay and polynomial space, enumeration runs in $O^*(1.89394^n)$.

This resolves the formalized “can the $1.8940$ chordal upper bound be improved?” question. It does not settle the broader optimum-base or improved-lower-bound problem.

Citation: Branching rules and correctness are from Abu-Khzam, Fernau, and Mann, “Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes,” arXiv:2208.05261, Section 7. The sharper numerical bound $1.89394$ is the arithmetic refinement given here.