Characterisation of forests with trivial game domination numbers

M. J. Nadjafi-Arani, Mark Siggers, Hossein Soltani

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

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 languageEnglish
Pages (from-to)800-811
Number of pages12
JournalJournal of Combinatorial Optimization
Volume32
Issue number3
DOIs
StatePublished - 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