A dual view of Roman Domination: The 2-limited packing problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914317683654656 |
|---|---|
| author | Bachtler, Oliver Krumke, Sven O. Weiß, Helena |
| author_facet | Bachtler, Oliver Krumke, Sven O. Weiß, Helena |
| contents | We consider the 2-limited packing problem: for a graph $G=(V,E)$ one seeks to find a maximum cardinality subset $B\subseteq V$, such that, for all $v\in V$, the closed neighbourhood of $v$ contains at most two vertices in $B$. We compare this packing problem to the well-known Roman domination problem by pointing out some similarities and differences in the behaviour of the optimal solutions of both problems and show that these two problems are weakly dual. We show that for trees, the two problems are strongly dual, letting us solve the Roman domination problem by computing an optimal solution to the 2-limited packing problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_19748 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A dual view of Roman Domination: The 2-limited packing problem Bachtler, Oliver Krumke, Sven O. Weiß, Helena Combinatorics 05C69, 05C05, 05C85 We consider the 2-limited packing problem: for a graph $G=(V,E)$ one seeks to find a maximum cardinality subset $B\subseteq V$, such that, for all $v\in V$, the closed neighbourhood of $v$ contains at most two vertices in $B$. We compare this packing problem to the well-known Roman domination problem by pointing out some similarities and differences in the behaviour of the optimal solutions of both problems and show that these two problems are weakly dual. We show that for trees, the two problems are strongly dual, letting us solve the Roman domination problem by computing an optimal solution to the 2-limited packing problem. |
| title | A dual view of Roman Domination: The 2-limited packing problem |
| topic | Combinatorics 05C69, 05C05, 05C85 |
| url | https://arxiv.org/abs/2601.19748 |