×

polish – Let us play the cleaning game. (English) Zbl 1258.91043

Summary: polish is a game based on the ‘Cleaning with Brushes’ model. It is a combinatorial game in the sense of Conway but can be seen as a graph searching or chip-firing problem as well. We consider only the impartial version and give a characterization of graphs with maximum degree two that are first player wins. We also show that the second player can win on the complete graph \(K_{n}\) provided n\(\geq 3\) and the complete bipartite graph \(K_{2,n}\) provided \(n \neq 1,3\). We give the nim-values for all positions on paths, stars, and also the nim-values for complete bipartite graphs where every vertex needs at most 3 more brushes to fire.

MSC:

91A46 Combinatorial games
91A43 Games involving graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, M. H.; Nowakowski, R. J.; Wolfe, D., Lessons in Play (2007), A K Peters, Ltd · Zbl 1184.91001
[2] Alon, N.; Prałat, P.; Wormald, N., Cleaning regular graphs with brushes, SIAM Journal on Discrete Mathematics, 23, 233-250 (2008) · Zbl 1187.05066
[3] Berlekamp, E. R.; Conway, J. H.; Guy, R. K., Winning Ways for Your Mathematical Plays, vol. 1 (2001), A K Peters, Ltd · Zbl 1005.00004
[4] Biedl, T.; Chan, T.; Ganjali, Y.; Hajiaghayi, M.; Wood, D., Balanced vertex-orderings of graphs, Discrete Applied Mathematics, 148, 1, 27-48 (2005) · Zbl 1060.05088
[5] Bjorner, A.; Lovasz, L.; Shor, P. W., Chip-firing games on graphs, European Journal of Combinatorics, 12, 283-291 (1991) · Zbl 0729.05048
[6] Conway, J. H., On Numbers and Games (2001), A K Peters, Ltd. · Zbl 0972.11002
[7] Fomin, F. V.; Thilikos, D. M., An annotated bibliography on guaranteed graph searching, Theoretical Computer Science, 399, 236-245 (2008) · Zbl 1160.68007
[8] Gaspers, S.; Messinger, M.-E.; Nowakowski, R.; Prałat, P., Clean the graph before you draw it!, Information Processing Letters, 109, 463-467 (2009) · Zbl 1209.68369
[9] Gaspers, S.; Messinger, M.-E.; Nowakowski, R.; Prałat, P., Parallel cleaning of a network with brushes, Discrete Applied Mathematics, 158, 467-478 (2009) · Zbl 1185.90024
[10] P. Gordinowicz, R. Nowakowski, P. Prałat, A. Siegel, French polish, preprint.; P. Gordinowicz, R. Nowakowski, P. Prałat, A. Siegel, French polish, preprint.
[11] Guo, A.; Miller, E., Lattice point methods for combinatorial games, Advances in Applied Mathematics, 46, 363-378 (2011) · Zbl 1213.91045
[12] B. Hobbs, J. Kahabka, Underwater cleaning technique used for removal of zebra mussels at the fitzpatrick nuclear power plan, in: Proceedings of The Fifth International Zebra Mussel and Other Aquatic Nuisance Organisms Conference, The Sea Grant Nonindigenous Species Site, 1995. (accessed 04.06.08), http://www.sgnis.org/publicat/47.htm; B. Hobbs, J. Kahabka, Underwater cleaning technique used for removal of zebra mussels at the fitzpatrick nuclear power plan, in: Proceedings of The Fifth International Zebra Mussel and Other Aquatic Nuisance Organisms Conference, The Sea Grant Nonindigenous Species Site, 1995. (accessed 04.06.08), http://www.sgnis.org/publicat/47.htm
[13] Kára, J.; Kratochvíl, J.; Wood, D., On the complexity of the balanced vertex ordering problem, Discrete Mathematics & Theoretical Computer Science, 9, 1, 193-202 (2007) · Zbl 1153.05037
[14] S.R. Kotler, E.C. Mallen, K.M. Tammus, Robotic removal of zebra mussel accumulations in a nuclear power plant screenhouse, in: Proceedings of The Fifth International Zebra Mussel and Other Aquatic Nuisance Organisms Conference, The Sea Grant Nonindigenous Species Site, 1995. (accessed 04.06.08) http://www.sgnis.org/publicat/113.htm; S.R. Kotler, E.C. Mallen, K.M. Tammus, Robotic removal of zebra mussel accumulations in a nuclear power plant screenhouse, in: Proceedings of The Fifth International Zebra Mussel and Other Aquatic Nuisance Organisms Conference, The Sea Grant Nonindigenous Species Site, 1995. (accessed 04.06.08) http://www.sgnis.org/publicat/113.htm
[15] Messinger, M.-E.; Nowakowski, R. J.; Prałat, P., Cleaning a network with brushes, Theoretical Computer Science, 399, 191-205 (2008) · Zbl 1187.68185
[16] Messinger, M. E.; Nowakowski, R.; Prałat, P., Cleaning with brooms, Graphs and Combinatorics, 27, 251-267 (2011) · Zbl 1235.05094
[17] Messinger, M.-E.; Nowakowski, R. J.; Prałat, P.; Wormald, N., Cleaning random \(d\)-regular graphs with brushes using a degree-greedy algorithm, (Proceedings of the 4th Workshop on Combinatorial and Algorithmic Aspects of Networking. Proceedings of the 4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007. Proceedings of the 4th Workshop on Combinatorial and Algorithmic Aspects of Networking. Proceedings of the 4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007, Lecture Notes in Computer Science, vol. 4852 (2007), Springer), 13-26 · Zbl 1136.05320
[18] Prałat, P., Cleaning random \(d\)-regular graphs with Brooms, Graphs and Combinatorics, 27, 567-584 (2011) · Zbl 1235.05126
[19] Prałat, P., Cleaning random graphs with brushes, Australasian Journal of Combinatorics, 43, 237-251 (2009) · Zbl 1155.05336
[20] Singmaster, D., Almost all games are first person games, Eureka, 41, 33-37 (1981)
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.