On $\{k\}$-Roman graphs: complexity of recognition and the case of split graphs

Abstract

For a positive integer $k$, a $\{k\}$-Roman dominating function of a graph $G=(V,E)$ is a function $f:V\to \{0,1,\dots ,k\}$ satisfying ${\sum }_{u\in N(v)}f(u)\ge k$ for each vertex $v\in V$ with $f(v)=0$. Every graph $G$ satisfies ${\gamma }_{\{Rk\}}(G)\le 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\ge 2$, the problem of recognizing \hbox{$\{k\}$-Roman} graphs is \textsf{NP}-hard, even for split graphs. For $k\ge 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.

An extended abstract of this work was accepted for the proceedings of the XIII Latin American Algorithms, Graphs, and Optimization Symposium (LAGOS 2025). Due to an update of this work, some of the former results are only available in previous ArXiv versions