Bujtás, Csilla and Tuza, Zsolt (2016) The Disjoint Domination Game. Discrete Mathematics, 339 (7). pp. 1985-1992. ISSN 0012-365X
|
Text
1411.5184v1.pdf Download (171kB) | Preview |
Abstract
We introduce and study a Maker-Breaker type game in which the issue is to create or avoid two disjoint dominating sets in graphs without isolated vertices. We prove that the maker has a winning strategy on all connected graphs if the game is started by the breaker. This implies the same in the (2:1) biased game also in the maker-start game. It remains open to characterize the maker-win graphs in the maker-start non-biased game, and to analyze the (a:b) biased game for (a:b)≠(2:1). For a more restricted variant of the non-biased game we prove that the maker can win on every graph without isolated vertices. © 2015 Elsevier B.V.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Games on graphs; Dominating set; Disjoint Domination Game; Combinatorial game; Biased game |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 15 Sep 2016 14:06 |
| Last Modified: | 15 Sep 2016 14:06 |
| URI: | http://real.mtak.hu/id/eprint/39567 |
Actions (login required)
 |
Edit Item |
