Characterisation of forests with trivial game domination numbers

M. J. Nadjafi-Arani (), Mark Siggers () and Hossein Soltani ()
Additional contact information
M. J. Nadjafi-Arani: Mahallat Institute of Higher Education
Mark Siggers: Kyungpook National University
Hossein Soltani: Institute for Advanced Studies in Basic Sciences

Journal of Combinatorial Optimization, 2016, vol. 32, issue 3, No 10, 800-811

Abstract: 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_*$$ A ∗ dominates the whole graph. The Dominator plays to minimise the size of the set $$A_*$$ A ∗ while the Staller plays to maximise it. A graph is $$D$$ D -trivial if when the Dominator plays first and both players play optimally, the set $$A_*$$ A ∗ is a minimum dominating set of the graph. A graph is $$S$$ S -trivial if the same is true when the Staller plays first. We consider the problem of characterising $$D$$ D -trivial and $$S$$ S -trivial graphs. We give complete characterisations of $$D$$ D -trivial forests and of $$S$$ S -trivial forests. We also show that $$2$$ 2 -connected $$D$$ D -trivial graphs cannot have large girth, and conjecture that the same holds without the connectivity condition.

Keywords: Domination number; Domination game; Game domination number; Tree; 05C57; 91A43; 05C69 (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9903-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:3:d:10.1007_s10878-015-9903-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9903-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().