20.500.12556/RUP-22209 On {k}-Roman graphs For 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. graph domination {k}-Roman domination {k}-Roman graph split graph split join NP-completeness dominacija v grafih {k}-rimska dominacija {k}-rimski graf razcepljen graf razcepljen spoj NP-polnost true false true Angleški jezik Slovenski jezik Neznano 2025-12-16 13:38:21 2025-12-16 13:38:22 2025-12-19 03:04:30 0000-00-00 00:00:00 2025 0 0 Str. 325-332 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1877-0509 261677571 10.1016/j.procs.2025.10.315 261688835 RAZ_Bester_Storgel_Kenny_2025.pdf RAZ_Bester_Storgel_Kenny_2025.pdf 1 86FD2CFC7C83B2842C196039D22EF8B5 c818d4310d80011c7bf04c907de5be2745e1a5480ec996e667ae323410b33f35 902546e4-da7c-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32241 https://www.sciencedirect.com/science/article/pii/S1877050925036622 1 69adb15e-da7c-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32240 Fakulteta za matematiko, naravoslovje in informacijske tehnologije Inštitut Andrej Marušič 0 0 0