A generalization of Arc-Kayles. (English) Zbl 1417.91143
Summary: The game Arc-Kayles is played on an undirected graph with two players taking turns deleting an edge and its endpoints from the graph. We study a generalization of this game, Weighted Arc-Kayles (WAK for short), played on graphs with counters on the vertices. The two players alternate choosing an edge and removing one counter on both endpoints. An edge can no longer be selected if any of its endpoints has no counter left. The last player to play a move wins. We give a winning strategy for WAK on trees of depth 2. Moreover, we show that the Grundy values of WAK and Arc-Kayles are unbounded. We also prove a periodicity result on the outcome of WAK when the number of counters is fixed for all the vertices but one. Finally, we show links between this game and a variation of the non-attacking queens game on a chessboard.
MSC:
| 91A46 | Combinatorial games |
| 91A43 | Games involving graphs |
| 91A05 | 2-person games |
| 05C57 | Games on graphs (graph-theoretic aspects) |
References:
| [1] | Adams R, Dixon J, Elder J, Peabody J, Vega O, Willis K (2016) Combinatorial analysis of a subtraction game on graphs. Int J Combin 2016:1476359 · Zbl 1370.05151 · doi:10.1155/2016/1476359 |
| [2] | Albert M, Nowakowski R, Wolfe D (2007) Lessons in play: an introduction to combinatorial game theory. CRC Press, Boca Raton · Zbl 1184.91001 · doi:10.1201/b10691 |
| [3] | Berkelamp ER, Conway JH, Guy RK (2001-2004) Winning ways for your mathematical plays, vols. 1-4, 2nd edn. A K Peters, Wellesley · Zbl 1005.00004 |
| [4] | Bodlaender HL, Kratsch D (2002) Kayles and nimbers. J Algorithms 43(1):106-119 · Zbl 1005.68112 · doi:10.1006/jagm.2002.1215 |
| [5] | Fleischer R, Trippen G (2006) Kayles on the way to the stars. In: Jaap van den Herik H et al (eds) Fourth international conference computers and games. LNCS Book Series, vol 3846. Springer, Berlin. https://doi.org/10.1007/11674399_16 |
| [6] | Guy RK, Smith CA (1956) The G-values of various games. In: Mathematical proceedings of the Cambridge Philosophical Society, vol 52, no. 03. Cambridge University Press, Cambridge, pp 514-526 · Zbl 0074.34503 |
| [7] | Huggan M (2015) Impartial intersection restriction games, Master’s thesis. Retrieved from Carleton University Research Virtual Environment (CURVE) (Record b3819898) |
| [8] | Lampis M, Mitsou V (2014) The computational complexity of the game of set and its theoretical applications. Latin American symposium on theoretical informatics. Springer, Berlin, pp 24-34 · Zbl 1405.68142 |
| [9] | Noon H, Van Brummelen G (2006) The non-attacking queens game. Coll Math J 37(3):223-227 · doi:10.2307/27646335 |
| [10] | O’Sullivan C (2017) A vertex and edge deletion game on graphs. arXiv:1709.01354 · Zbl 1417.91137 |
| [11] | Schaeffer TJ (1978) On the complexity of some two-person perfect-information games. J Comput Syst Sci 16(2):185-225. https://doi.org/10.1016/0022-0000(78)90045-4 · Zbl 0383.90112 · doi:10.1016/0022-0000(78)90045-4 |
| [12] | Siegel AN (2013) Combinatorial game theory, vol 146. American Mathematical Society, Providence · Zbl 1288.91003 · doi:10.1090/gsm/146 |
| [13] | Sprague R (1935) Über mathematische Kampfspiele. Tohoku Math J First Ser 41:438-444 · Zbl 0013.29004 |
| [14] | Stevens B, Huggan M (2016) Polynomial time graph families for Arc-Kayles. INTEGERS 16:2 · Zbl 1371.05180 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
