Abstract
In the domination game, two players, the Dominator and Staller, take turns adding vertices of a fixed graph to a set, at each turn increasing the number of vertices dominated by the set, until the final set A∗ dominates the whole graph. The Dominator plays to minimise the size of the set A∗ while the Staller plays to maximise it. A graph is D-trivial if when the Dominator plays first and both players play optimally, the set A∗ is a minimum dominating set of the graph. A graph is S-trivial if the same is true when the Staller plays first. We consider the problem of characterising D-trivial and S-trivial graphs. We give complete characterisations of D-trivial forests and of S-trivial forests. We also show that 2 -connected D-trivial graphs cannot have large girth, and conjecture that the same holds without the connectivity condition.
| Original language | English |
|---|---|
| Pages (from-to) | 800-811 |
| Number of pages | 12 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 32 |
| Issue number | 3 |
| DOIs | |
| State | Published - 1 Oct 2016 |
Keywords
- Domination game
- Domination number
- Game domination number
- Tree
Fingerprint
Dive into the research topics of 'Characterisation of forests with trivial game domination numbers'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver