Characterisation of forests with trivial game domination numbers |
| |
Authors: | M J Nadjafi-Arani Mark Siggers Hossein Soltani |
| |
Institution: | 1.Faculty of Science,Mahallat Institute of Higher Education,Mahallat,Islamic Republic of Iran;2.Kyungpook National University,Daegu,Republic of Korea;3.Institute for Advanced Studies in Basic Sciences,Zanjan,Iran |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|