{"ID":2864117,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.23615","arxiv_id":"2509.23615","title":"Hardness and Algorithmic Results for Roman \\{3\\}-Domination","abstract":"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].","short_abstract":"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 \\i...","url_abs":"https://arxiv.org/abs/2509.23615","url_pdf":"https://arxiv.org/pdf/2509.23615v1","authors":"[\"Sangam Balchandar Reddy\"]","published":"2025-09-28T03:33:33Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}