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.
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)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。