1.
On {k}-Roman graphsKenny Bešter Štorgel,
Nina Chiarelli,
Lara Fernández,
J. Pascal Gollin,
Claire Hilaire,
Valeria Alejandra Leoni,
Martin Milanič, 2025, objavljeni znanstveni prispevek na konferenci
Opis: 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.
Ključne besede: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Objavljeno v RUP: 16.12.2025; Ogledov: 243; Prenosov: 2
Celotno besedilo (395,09 KB)
Gradivo ima več datotek! Več...
