Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.05674 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910009409929216 |
|---|---|
| author | Štorgel, Kenny Bešter Chiarelli, Nina Fernández, Lara Gollin, J. Pascal Hilaire, Claire Leoni, Valeria Milanič, Martin |
| author_facet | Štorgel, Kenny Bešter Chiarelli, Nina Fernández, Lara Gollin, J. Pascal Hilaire, Claire Leoni, Valeria Milanič, Martin |
| contents | For a positive integer $k$, a $\{k\}$-Roman dominating function of a graph $G = (V,E)$ is a function $f\colon V \rightarrow \{0,1,\ldots,k\}$ satisfying $f (N(v)) \geq k$ for each vertex $v\in V$ with $f (v) = 0$. Every graph $G$ satisfies $γ_{\{Rk\}}(G) \leq 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 \emph{$\{k\}$-Roman graphs}. This extends the concept of $\{k\}$-Roman trees studied by Wang et al. in 2021 to general graphs. We prove that for every $k\geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_05674 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On $\{k\}$-Roman graphs: complexity of recognition and the case of split graphs Štorgel, Kenny Bešter Chiarelli, Nina Fernández, Lara Gollin, J. Pascal Hilaire, Claire Leoni, Valeria Milanič, Martin Combinatorics 05C69 (Primary) 05C65, 68Q25 (Secondary) For a positive integer $k$, a $\{k\}$-Roman dominating function of a graph $G = (V,E)$ is a function $f\colon V \rightarrow \{0,1,\ldots,k\}$ satisfying $f (N(v)) \geq k$ for each vertex $v\in V$ with $f (v) = 0$. Every graph $G$ satisfies $γ_{\{Rk\}}(G) \leq 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 \emph{$\{k\}$-Roman graphs}. This extends the concept of $\{k\}$-Roman trees studied by Wang et al. in 2021 to general graphs. We prove that for every $k\geq 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. |
| title | On $\{k\}$-Roman graphs: complexity of recognition and the case of split graphs |
| topic | Combinatorics 05C69 (Primary) 05C65, 68Q25 (Secondary) |
| url | https://arxiv.org/abs/2511.05674 |