On {k}-Roman graphsBešter Štorgel, Kenny (Avtor) Chiarelli, Nina (Avtor) Fernández, Lara (Avtor) Gollin, J. Pascal (Avtor) Hilaire, Claire (Avtor) Leoni, Valeria Alejandra (Avtor) Milanič, Martin (Avtor) graph domination{k}-Roman domination{k}-Roman graphsplit graphsplit joinNP-completenessFor a positive integer k, a {k}-Roman dominating function of a graph G = (V, E) is a function f : V → {0, 1, . . . , k} satisfying f (N(v)) ≥ k for each vertex v ∈ V with f (v) = 0. Every graph G satisfies γ{Rk}(G) ≤ kγ(G), where γ{Rk}(G) denotes the minimum weight of a {k}-Roman dominating function of G and γ(G) is the domination number of G. In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of {k}-Roman trees studied by Wang et al. in 2021 to gen- eral graphs. We prove that for every k ≥ 3, the problem of recognizing {k}-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the {k}-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.20252025-12-16 13:38:21Neznano22209UDK: 519.17ISSN pri članku: 1877-0509OceCobissID: 261677571DOI: 10.1016/j.procs.2025.10.315COBISS.SI-ID: 261688835sl