View PDF

Abstract:For a positive integer $k$, a $\{k\}$-Roman dominating function of a graph $G = (V,E)$ is a function $f\colon V \rightarrow \{0,1,\ldots,k\}$ satisfying $\sum_{u\in N(v)} f(u) \geq k$ for each vertex $v\in V$ with $f (v) = 0$. Every graph $G$ satisfies $\gamma_{\{Rk\}}(G) \leq k\gamma(G)$, where $\gamma(G)$ is the domination number of $G$ and $\gamma_{\{Rk\}}(G)$ denotes the $\{k\}$-Roman domination number of $G$, that is, the minimum value of $\sum_{u\in V(G)} f(u)$ over all $\{k\}$-Roman dominating functions of $G$.
In this work we study graphs for which the equality is reached, called \emph{$\{k\}$-Roman graphs}. This extends the concept of $\{k\}$-Roman trees studied by Wang et al.~in 2021 to general graphs. We prove that for every $k\geq 2$, the problem of recognizing \hbox{$\{k\}$-Roman} graphs is \textsf{NP}-hard, even for split graphs. For ${k\geq 3}$, we give an alternative proof by generalizing several known results on domination in middle graphs to the hypergraph setting. Finally, we characterize the \kr property within two specific subclasses of split graphs: suns and their complements.

Submission history

From: Lara Fernandez [view email]
[v1] Fri, 7 Nov 2025 19:26:58 UTC (45 KB)
[v2] Wed, 12 Nov 2025 03:22:30 UTC (45 KB)
[v3] Mon, 2 Feb 2026 19:04:56 UTC (45 KB)
[v4] Thu, 6 Aug 2026 14:41:52 UTC (48 KB)