Hardness and Algorithmic Results for Roman \{3\}-Domination
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918149839912960 |
|---|---|
| author | Reddy, Sangam Balchandar |
| author_facet | Reddy, Sangam Balchandar |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23615 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hardness and Algorithmic Results for Roman \{3\}-Domination Reddy, Sangam Balchandar Computational Complexity Data Structures and Algorithms 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]. |
| title | Hardness and Algorithmic Results for Roman \{3\}-Domination |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.23615 |