TY - JOUR
T1 - Characterisation of forests with trivial game domination numbers
AU - Nadjafi-Arani, M. J.
AU - Siggers, Mark
AU - Soltani, Hossein
N1 - Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2016/10/1
Y1 - 2016/10/1
N2 - 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.
AB - 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.
KW - Domination game
KW - Domination number
KW - Game domination number
KW - Tree
UR - http://www.scopus.com/inward/record.url?scp=84929649970&partnerID=8YFLogxK
U2 - 10.1007/s10878-015-9903-9
DO - 10.1007/s10878-015-9903-9
M3 - Article
AN - SCOPUS:84929649970
SN - 1382-6905
VL - 32
SP - 800
EP - 811
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 3
ER -