标题： 罗马\{3\}支配的难度和算法结果 显示英文标题

标题： Hardness and Algorithmic Results for Roman \{3\}-Domination

摘要： 一个罗马$\{3\}$-支配函数在图$G = (V, E)$上是一个函数$f: V \rightarrow \{0, 1, 2, 3\}$，使得对于每个顶点$u \in V$，如果$f(u) = 0$则$\sum_{v \in N(u)} f(v) \geq 3$并且如果$f(u) = 1$则$\sum_{v \in N(u)} f(v) \geq 2$。 一个罗马$\{3\}$-支配函数$f$的权是$\sum_{u \in V} f(u)$。\rtd{}的目标是计算一个权最小的罗马$\{3\}$-支配函数。该问题已知在弦图、星凸二部图和梳凸二部图上是 NP 完全的。在本文中，我们研究\rtd{}的复杂性，并证明该问题在分割图上是 NP 完全的。此外，我们证明该问题在以权为参数时是 W[2]-难的。在积极方面，我们为块图提出了一种多项式时间算法，从而解决了 Chaudhary 和 Pradhan [离散应用数学, 2024] 提出的一个开放性问题。 显示英文摘要

摘要： A Roman $\{3\}$-dominating function on a graph $G = (V, E)$ is a function $f: V \rightarrow \{0, 1, 2, 3\}$ such that for each vertex $u \in V$, if $f(u) = 0$ then $\sum_{v \in N(u)} f(v) \geq 3$ and if $f(u) = 1$ then $\sum_{v \in N(u)} f(v) \geq 2$. The weight of a Roman $\{3\}$-dominating function $f$ is $\sum_{u \in V} f(u)$. The objective of \rtd{} is to compute a Roman $\{3\}$-dominating function of minimum weight. The problem is known to be NP-complete on chordal graphs, star-convex bipartite graphs and comb-convex bipartite graphs. In this paper, we study the complexity of \rtd{} and show that the problem is NP-complete on split graphs. In addition, we prove that the problem is W[2]-hard parameterized by weight. On the positive front, we present a polynomial-time algorithm for block graphs, thereby resolving an open question posed by Chaudhary and Pradhan [Discrete Applied Mathematics, 2024].