| Naslov: | On {k}-Roman graphs |
|---|
| Avtorji: | ID Bešter Štorgel, Kenny (Avtor)
ID Chiarelli, Nina (Avtor)
ID Fernández, Lara (Avtor)
ID Gollin, J. Pascal (Avtor)
ID Hilaire, Claire (Avtor)
ID Leoni, Valeria Alejandra (Avtor)
ID Milanič, Martin (Avtor) |
|---|
| Datoteke: |  RAZ_Bester_Storgel_Kenny_2025.pdf (395,09 KB)
MD5: 86FD2CFC7C83B2842C196039D22EF8B5
 https://www.sciencedirect.com/science/article/pii/S1877050925036622
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Neznano |
|---|
| Tipologija: | 1.08 - Objavljeni znanstveni prispevek na konferenci |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
IAM - Inštitut Andrej Marušič
|
|---|
| 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 |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | Str. 325-332 |
|---|
| PID: | 20.500.12556/RUP-22209  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1877-0509 |
|---|
| DOI: | 10.1016/j.procs.2025.10.315 |
|---|
| COBISS.SI-ID: | 261688835 |
|---|
| Datum objave v RUP: | 16.12.2025 |
|---|
| Število ogledov: | 176 |
|---|
| Število prenosov: | 2 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
