On a modular domination game

✍ Scribed by Sylvain Gravier; Mehdi Mhalla; Eric Tannier

• Book ID: 104325869
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 314 KB
• Volume: 306
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00285-8

✦ Synopsis

We present a generalization of the so-called -game, introduced by Sutner (Math. Intelligencer 11 (1989) 49), a combinatorial game played on a graph, with relations to cellular automata, as well as odd domination in graphs. A conÿguration on a graph is an assignment of values in {0; : : : ; p -1} (where p is an arbitrary positive integer) to all the vertices of G. One may think of a vertex v of G as a button the player can press at his discretion. If vertex v is chosen, the value of all the vertices adjacent to v increases by 1 modulo p. This deÿnes an equivalence relation between the conÿgurations: two conÿgurations are in relation if it is possible to reach one from the other by a sequence of such operations. We investigate the number of equivalence classes that a given graph has, and we give formulas for trees and special regular graphs.