A codex of \(\mathcal{N}\)- and \(\mathcal{P}\)-positions in Harary’s ‘caterpillar game’. (English) Zbl 1475.91043
Summary: Frank Harary proposed the following game: Given a caterpillar \(C\), two players take turns removing edges of a path. The player who takes the last edge wins the game. In this paper, we completely characterize the \(\mathcal{N}\)- and \(\mathcal{P}\)-positions for all caterpillars with spine length zero, one, two and three. Furthermore, we analyze approximately 94% of the caterpillars with spine length greater than or equal to four. In those cases, they all turn out to be \(\mathcal{N}\)-positions.
References:
| [1] | Games of No Chance 3. Papers from the Combinatorial Game Theory Workshop held in Banff, AB, June 2005. Edited by Michael H. Albert and Richard J. Nowakowski. Mathematical Sciences Research Institute Publications,56. Cambridge University Press, Cambridge, 2009. x+575 pp. ISBN: 978-0-521-67854-4. |
| [2] | M.H. Albert, R.J. Nowakowski and D. Wolfe.Lessons in Play: An Introduction to Combinatorial Game Theory, A K Peters Ltd., Wellesley, Massachusetts, (2007). · Zbl 1184.91001 |
| [3] | E.R. Berlekamp, J.H. Conway and R.K. Guy.Winning Ways for Your Mathematical Plays, (four volumes, 2nd edition), A K Peters Ltd., Wellesley, Massachusetts, (2001). · Zbl 1005.00004 |
| [4] | L. Blanc, E. Duchˆene and S. Gravier. A deletion game on graphs: “Le Pic Arˆete”,Integers.6 (2006), #G2, 10pp. (electronic). · Zbl 1134.91305 |
| [5] | N.J. Calkin, K. James, J.E. Janoski, S. Leggett, B. Richards, N. Sitaraman and S.M. Thomas. Computing strategies for graphical Nim,Congr. Numer.202(2010), 171-185. · Zbl 1229.05209 |
| [6] | G. Chartrand and L. Lesniak.Graphs and Digraphs, 2nd Edition, Wadsworth & Brooks/Cole, Pacific Grove, California, (1986). · Zbl 0666.05001 |
| [7] | J.H. Conway.On Numbers and Games, 2nd Edition, A K Peters Ltd., Wellesley, Massachusetts, (2001). · Zbl 0972.11002 |
| [8] | A. Dailly, V. Gledel and M. Heinrich. A generalization of Arc-Kayles,Internat. J. Game Theory.48(2019), no. 2, 491-511. · Zbl 1417.91143 |
| [9] | Z. Dziechci´nska-Halamoda, Z. Majcher, J. Michael and Z. Skupie´n. A Sokoban-type game and arc deletion within irregular digraphs of all sizes,Discuss. Math. Graph Theory.27(2007), no. 3, 611-622. · Zbl 1142.05036 |
| [10] | L.A. Erickson.The Game of Nim on Graphs.Ph.D. Thesis - North Dakota State University. 2011. 64pp. |
| [11] | A.S. Fraenkel. Combinatorial games: selected bibliography with a succinct gourmet introduction,Electron. J. Combin. (2012), Dynamic Survey #DS2. · Zbl 1062.91016 |
| [12] | A.S. Fraenkel and E.R. Scheinerman. A deletion game on hypergraphs,Discrete Appl. Math. 30(1991), no. 2-3, 155-162. · Zbl 0728.90106 |
| [13] | M. Fukuyama. A Nim game played on graphs. II,Theoret. Comput. Sci.304(1-3), (2003), 401-419. · Zbl 1041.91019 |
| [14] | M. Fukuyama. A Nim game played on graphs,Theoret. Comput. Sci.304(1-3), (2003), 387-399. · Zbl 1041.91018 |
| [15] | F. Harary. Lecture (35th Southeastern Conference on Combinatorics, Graph Theory and Computing), Baton Rouge, LA, March 2001. |
| [16] | P. Harding and P. Ottaway. Edge deletion games with parity rules,Integers.14(2014), #G1, 10pp. (electronic). · Zbl 1285.05122 |
| [17] | M. Huggan and B. Stevens. Polynomial time graph families for Arc Kayles,Integers.16 (2016), #A86, 14pp. (electronic). · Zbl 1371.05180 |
| [18] | M. Kano. An edge-removing game on a graph (a generalization of Nim and Kayles), Surikaisekikenkyusho Kokyuroku No. 820, (1993), 82-90. |
| [19] | Games of No Chance 5. Papers from the Combinatorial Game Theory Workshop held at the Banff International Research Station (BIRS), January 2011. Edited by Urban Larsson. Mathematical Sciences Research Institute Publications,70. Cambridge University Press, Cambridge, 2019. viii+490 pp. ISBN: 978-1-108-48580-7; 978-1-108-71365-8. |
| [20] | R.M. Low and W.H. Chan. Notes on the combinatorial game: Graph Nim,Electron. J. Graph Theory Appl.4(2016), no. 2, 190-205. · Zbl 1467.05173 |
| [21] | L. Merchant. Nim on the complete graph,Ars Combin.119(2015), 117-127. · Zbl 1349.05237 |
| [22] | Games of No Chance 4. Selected papers from the Banff International Research Station (BIRS) Workshop on Combinatorial Games held in Banff, AB, 2008. Edited by Richard J. Nowakowski. Mathematical Sciences Research Institute Publications,63. Cambridge University Press, New York, 2015. x+339 pp. ISBN: 978-1-107-01103-8. |
| [23] | More Games of No Chance. Proceedings of the 2nd Combinatorial Games Theory Workshop held in Berkeley, CA, July 24-28, 2000. Edited by Richard J. Nowakowski. Mathematical Sciences Research Institute Publications,42. Cambridge University Press, Cambridge, 2002. xii+535 pp. ISBN: 0-521-80832-4. |
| [24] | Games of No Chance. Papers from the Combinatorial Game Theory Workshop held in Berkeley, CA, July 11-21, 1994. Edited by Richard J. Nowakowski. Mathematical Sciences Research Institute Publications,29. Cambridge University Press, Cambridge, 1996. xii+537 pp. ISBN: 0-521-57411-0. |
| [25] | C. O’Sullivan. A vertex and edge deletion game on graphs,Integers.18(2018), #G03, 38pp. (electronic). · Zbl 1417.91137 |
| [26] | A.N. Siegel,Combinatorial Game Theory, Graduate Studies in Mathematics,146, American Mathematical Society, Providence, RI. 523pp. (2013), ISBN: 978-0-8218-5190-6 · Zbl 1288.91003 |
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.
