The Lights Out Game on Directed Graphs

2023/06/09 by Dettling, T. Elise, Parker, Darren B.
#05C20 (Primary) #05C40 (Secondary) #05C50 (Primary) #05C57 (Primary) #05C78 (Primary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2306.06017

Abstract

We study a version of the lights out game played on directed graphs. For a digraph D, we begin with a labeling of V(D) with elements of ℤ_k for k ≥ 2. When a vertex v is toggled, the labels of v and any vertex that v dominates are increased by 1 mod k. The game is won when each vertex has label 0. We say that D is k-Always Winnable (also written k-AW) if the game can be won for every initial labeling with elements of ℤ_k. We prove that all acyclic digraphs are k-AW for all k, and we reduce the problem of determining whether a graph is k-AW to the case of strongly connected digraphs. We then determine winnability for tournaments with a minimum feedback arc set that arc-induces a directed path or directed star digraph.

Related

• Some Winnability Results for the Neighborhood and Group Labeling Lights Out Games
• An Extremal Problem for the Neighborhood Lights Out Game
• Lights Out on graphs
• On the Nature and Complexity of an Impartial Two-Player Variant of the Game Lights-Out
• Lights Out On Nearly Complete Graphs