| Title: | On {k}-Roman graphs |
|---|
| Authors: | ID Bešter Štorgel, Kenny (Author)
ID Chiarelli, Nina (Author)
ID Fernández, Lara (Author)
ID Gollin, J. Pascal (Author)
ID Hilaire, Claire (Author)
ID Leoni, Valeria Alejandra (Author)
ID Milanič, Martin (Author) |
|---|
| Files: |  RAZ_Bester_Storgel_Kenny_2025.pdf (395,09 KB)
MD5: 86FD2CFC7C83B2842C196039D22EF8B5
 https://www.sciencedirect.com/science/article/pii/S1877050925036622
|
|---|
| Language: | English |
|---|
| Work type: | Unknown |
|---|
| Typology: | 1.08 - Published Scientific Conference Contribution |
|---|
| Organization: | FAMNIT - Faculty of Mathematics, Science and Information Technologies
IAM - Andrej Marušič Institute
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness |
|---|
| Publication version: | Version of Record |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | Str. 325-332 |
|---|
| PID: | 20.500.12556/RUP-22209  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1877-0509 |
|---|
| DOI: | 10.1016/j.procs.2025.10.315 |
|---|
| COBISS.SI-ID: | 261688835 |
|---|
| Publication date in RUP: | 16.12.2025 |
|---|
| Views: | 212 |
|---|
| Downloads: | 2 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
