Abstract
In a vertex-colored graph, a set of vertices (Formula presented.) is said to be a rainbow set if every color in the graph appears exactly once in (Formula presented.). We investigate the complexities of various problems dealing with domination in vertex-colored graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, and of rainbow identifying sets), including when we ask for a unique solution: we show equivalence between these complexities and those of the well-studied Boolean satisfiability problems.
| Original language | English |
|---|---|
| Pages (from-to) | 1547-1572 |
| Number of pages | 26 |
| Journal | International Transactions in Operational Research |
| Volume | 29 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 1 May 2022 |
Keywords
- complexity theory
- dominating codes
- graph theory
- identifying codes
- locating-dominating codes
- rainbow sets
- twin-free graphs
- uniqueness of solution