×

Vertex Nim played on graphs. (English) Zbl 1278.91029

Summary: Given a graph \(G\) with positive integer weights on the vertices, and a token placed on some current vertex \(u\), two players alternately remove a positive integer weight from \(u\) and then move the token to a new current vertex adjacent to \(u\). When the weight of a vertex is set to 0, it is removed and its neighborhood becomes a clique. The player making the last move wins. This adaptation of Nim on graphs is called Vertexnim, and slightly differs from the game Vertex NimG introduced by Stockman in 2004. Vertexnim can be played on both directed or undirected graphs. In this paper, we study the complexity of deciding whether a given game position of Vertexnim is winning for the first or second player. In particular, we show that for undirected graphs, this problem can be solved in quadratic time. Our algorithm is also available for the game Vertex NimG, thus improving Stockman’s exptime algorithm. In the directed case, we are able to compute the winning strategy in polynomial time for several instances, including circuits or digraphs with self loops.

MSC:

91A46 Combinatorial games
91A43 Games involving graphs
91A05 2-person games
05C57 Games on graphs (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Berlekamp, E.; Conway, J. H.; Guy, R. K., Winning Ways for Your Mathematical Plays, vol. 1 (2001), A K Peters, Ltd.: A K Peters, Ltd. Natick, MA · Zbl 1005.00004
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), McMillan, Elsevier: McMillan, Elsevier London, New York · Zbl 1226.05083
[3] Bouton, C. L., Nim, a game with a complete mathematical theory, Ann. Math., 3, 35-39 (1905) · JFM 32.0225.02
[4] Burke, K.; George, O., A PSPACE-complete Graph Nim, submitted for publication · Zbl 1444.91051
[5] Duchêne, E.; Gravier, S., Geometrical extensions of Wythoffʼs game, Discrete Math., 309, 3595-3608 (2009) · Zbl 1165.91007
[6] Dufour, M.; Heubach, S., Circular Nim games, Electron. J. Comb., 20, 2 (2013) · Zbl 1266.91016
[7] Erickson, L., Nim on the complete graph (2010)
[8] Fraenkel, A. S., How to beat your Wythoff gamesʼ opponent on three fronts, Am. Math. Mon., 89, 353-361 (1982) · Zbl 0504.90087
[9] Fraenkel, A. S., The Raleigh game, (Combinatorial Number Theory (2007), de Gruyter: de Gruyter Berlin), 199-208 · Zbl 1178.91037
[11] Fraenkel, A. S.; Borosh, I., A generalization of Wythoffʼs game, J. Comb. Theory, Ser. A, 15, 175-191 (1973) · Zbl 0265.90065
[12] Fraenkel, A. S.; Simonson, S., Geography, Theor. Comput. Sci., 110, 197-214 (1993) · Zbl 0799.90145
[13] Fraenkel, A. S.; Zusman, D., A new heap game, Theor. Comput. Sci., 252, 5-12 (2001) · Zbl 0986.91002
[14] Fraenkel, A. S., Complexity, appeal and challenges of combinatorial games, Theor. Comput. Sci., 313, 393-415 (2004) · Zbl 1066.91017
[15] Fukuyama, M., A Nim game played on graphs, Theor. Comput. Sci., 304, 387-399 (2003) · Zbl 1041.91018
[16] Fukuyama, M., A Nim game played on graphs II, Theor. Comput. Sci., 304, 401-419 (2003) · Zbl 1041.91019
[17] Stockman, G., Presentation: The game of Nim on graphs: NimG (2004), available at
[18] Wythoff, W. A., A modification of the game of Nim, Nieuw Arch. Wiskd., 7, 199-202 (1907) · JFM 37.0261.03
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.