×

Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? (English) Zbl 1169.91011

Each vertex in a simple graph is in one of two states: “on” or “off”. The set of all on vertices is called a configuration. In the \(\sigma \)-game, “pushing” a vertex \(v\) changes the state of all vertices in the open neighborhood of \(v\), while in the \(\sigma ^{+}\)-game pushing \(v\) changes the state of all vertices in its closed neighborhood. The reachability question for these two games is to decide whether a given configuration can be reached from a given starting configuration by a sequence of pushes. The lit-only restriction allows a vertex to be pushed only if it is in the on state. It is shown that the lit-only restriction can make a big difference for reachability in the \(\sigma \)-game, but has essentially no effect in the \(\sigma ^{+}\)-game.

MSC:

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

References:

[1] Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., Complexity of reachability problems for finite discrete dynamical systems, J. Comput. System Sci., 72, 1317-1345 (2006) · Zbl 1119.68095
[2] Broersma, H.; Li, X., On the complexity of dominating set problems related to the minimum all-ones problem, Theoret. Comput. Sci., 385, 60-70 (2007) · Zbl 1124.68076
[3] Brouwer, A. E., Button madness
[4] Chartrand, G.; Zhang, P., Introduction to Graph Theory, Section 13.3 (2005), McGraw-Hill
[5] Chen, W. Y.C.; Li, X.; Wang, C.; Zhang, X., The minimum all-ones problem for trees, SIAM J. Comput., 33, 379-392 (2004) · Zbl 1056.05133
[6] Chuah, M.-K.; Hu, C.-C., Extended Vogan diagrams, J. Algebra, 301, 112-147 (2006) · Zbl 1147.17018
[7] Chuah, M.-K.; Hu, C.-C., A quick proof on the equivalence classes of extended Vogan diagrams, J. Algebra, 313, 824-827 (2007) · Zbl 1148.17012
[8] Das, A. K.; Nayak, T. K.; Chaudhuri, P. P., On characterization of state transition graph of additive cellular automata based on depth, Inform. Sci., 65, 189-224 (1992) · Zbl 0825.68470
[9] Y. Dodis, P. Winkler, Universal configurations in light-flipping games, in: Proc. of 12th Annunal ACM/SIAM Symposium on Discrete Algorithms, SODA, January 2001, pp. 926-927; Y. Dodis, P. Winkler, Universal configurations in light-flipping games, in: Proc. of 12th Annunal ACM/SIAM Symposium on Discrete Algorithms, SODA, January 2001, pp. 926-927 · Zbl 1004.91015
[10] Donnelly, R. G., Eriksson’s numbers game and finite Coxeter groups, Eur. J. Combin. (2008) · Zbl 1146.91012
[11] Eriksson, H.; Eriksson, K.; Sjöstrand, J., Note on the lamp lighting problem, Adv. Appl. Math., 27, 357-366 (2001), (Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000)) · Zbl 0995.05096
[12] Eriksson, K., Reachability is decidable in the numbers game, Theoret. Comput. Sci., 131, 431-439 (1994) · Zbl 0820.90149
[13] Fraenkel, A., Virus versus mankind, Lect. Notes Comput. Sci., 2063, 204-213 (2001) · Zbl 1001.91010
[14] Fraenkel, A., Two-player games on cellular automata, (More Games of No Chance (Berkeley, CA, 2000). More Games of No Chance (Berkeley, CA, 2000), Math. Sci. Res. Inst. Publ., 42 (2002), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 279-306 · Zbl 1109.91324
[15] Fraenkel, A., Mathematical chats between two physicists, (Wolfe, D.; Rodgers, T., Puzzler’s Tribute: A Feast for the Mind (2002)), 383-386, Honoring Martin Gardner, A.K. Peters, Natick, MA
[16] Goldwasser, J. L.; Klostermeyer, W. F., Maximization versions of “lights out” games in grids and graphs, Congr. Numer., 126, 99-111 (1997) · Zbl 0897.05048
[17] Goldwasser, J. L.; Klostermeyer, W. F., Parity dominating sets in grid graphs, Congr. Numer., 172, 79-96 (2005) · Zbl 1091.05050
[18] J.L. Goldwasser, W.F. Klostermeyer, The \(\sigma \); J.L. Goldwasser, W.F. Klostermeyer, The \(\sigma \) · Zbl 1177.91058
[19] J.L. Goldwasser, M. Li, Y. Wu, Lit-only sigma game on a path (in preparation); J.L. Goldwasser, M. Li, Y. Wu, Lit-only sigma game on a path (in preparation)
[20] J.L. Goldwasser, X. Wang, Y. Wu, Extremal configurations achieving large light number for lit-only sigma game (in preparation); J.L. Goldwasser, X. Wang, Y. Wu, Extremal configurations achieving large light number for lit-only sigma game (in preparation)
[21] Gravier, S.; Jorrand, P.; Mhalla, M.; Payan, C., Quantum octal game, Int. J. Found. Comput. Sci., 17, 919-931 (2006) · Zbl 1116.91029
[22] Halldórsson, M. M.; Kratochvíl, J.; Telle, J. A., Mod-2 independence and domination in graphs, Lect. Notes Comput. Sci., 1665, 101-109 (1999) · Zbl 0943.05081
[23] H-W. Huang, C-W. Weng, Combinatorial representations of Coxeter groups over a field of two elements, arXiv:0804.2150; H-W. Huang, C-W. Weng, Combinatorial representations of Coxeter groups over a field of two elements, arXiv:0804.2150
[24] Hunziker, M.; Machiavelo, A.; Park, J., Chebyshev polynomials over finite fields and reversibility of \(\sigma \)-automata on square grids, Theoret. Comput. Sci., 320, 465-483 (2004) · Zbl 1068.68089
[25] Kocik, J., Harmonic evolutions on graphs, Int. J. Math. Comput. Sci., 2, 65-82 (2007) · Zbl 1139.05035
[26] Li, X.; Wang, C.; Zhang, X., The general \(\sigma\) all-ones problem for trees, Discrete Appl. Math. (2007)
[27] Marino, M. C.; Sciriha, I.; Simić, S. K.; Tošić, D. V., More about singular line graphs of trees, Publ. Inst. Math. (Beograd) (N.S.), 79, 1-12 (2006) · Zbl 1121.05073
[28] F. Meunier, Pleins étiquetages et configurations équilibrées: aspects topologiques de l’optimisation combinatoire, PhD thesis, Université Joseph Fourier Grenoble I, 2006, http://www.enpc.fr/lvmt/frederic.meunier/These.pdf; F. Meunier, Pleins étiquetages et configurations équilibrées: aspects topologiques de l’optimisation combinatoire, PhD thesis, Université Joseph Fourier Grenoble I, 2006, http://www.enpc.fr/lvmt/frederic.meunier/These.pdf
[29] Muetze, T., Generalized switch-setting problems, Discrete Math., 307, 2755-2770 (2007) · Zbl 1127.05100
[30] Perrin, D.; Pin, J-E., Infinite Words: Automata, Semigroups, Logic and Games (2004), Elsevier · Zbl 1094.68052
[31] Pinchasi, R., Linear algebra approach to geometric graphs, J. Combin. Theory A, 114, 1363-1374 (2007) · Zbl 1125.05069
[32] Scherphuis, J., The mathematics of lights out
[33] Sciriha, I., On singular line graphs of trees, Congr. Numer., 135, 73-91 (1998) · Zbl 0952.05047
[34] Soma, N. Y.; Melo, J. P., On irreversibility of von Neumann additive cellular automata on grids, Discrete Appl. Math., 154, 861-866 (2006) · Zbl 1092.68061
[35] Sutner, K., Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11, 49-53 (1989) · Zbl 0770.68094
[36] Sutner, K., Cellular automata and intermediate reachability problems, Fund. Inform., 52, 249-256 (2002) · Zbl 1011.68061
[37] X. Wang, Y. Wu, Sigma-game on trees: Covering radius and tree order, manuscript; X. Wang, Y. Wu, Sigma-game on trees: Covering radius and tree order, manuscript
[38] Wang, X.; Wu, Y., Minimum light number of lit-only \(\sigma \)-game on a tree, Theoret. Comput. Sci., 381, 292-300 (2007) · Zbl 1188.68207
[39] Wu, Y., Even poset and a parity result for binary linear code, Linear Algebra Appl., 418, 591-594 (2006) · Zbl 1106.05056
[40] Wu, Y., Lit-only sigma game on a line graph, Eur. J. Combin. (2008)
[41] Zaidenberg, M., Periodic binary harmonic functions on lattices, Adv. Appl. Math., 40, 225-265 (2008) · Zbl 1165.11019
[42] M. Zaidenberg, Convolution equations on lattices: Periodic solutions with values in a prime characteristic field, arXiv:math-ph/0606070v3; M. Zaidenberg, Convolution equations on lattices: Periodic solutions with values in a prime characteristic field, arXiv:math-ph/0606070v3
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.