The Lights Out Game on Directed Graphs

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 \(\mathbb{Z}_k\) for \(k \ge 2\). When a vertex \(v\) is toggled, the labels of \(v\) and any vertex that \(v\) dominates are increased by 1 mod \(k\). The...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-06
Main Authors: Dettling, T Elise, Parker, Darren B
Format: Article
Language:English
Subjects:
Games
Graph theory
Graphs
Labeling
Labels
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\mathbb{Z}_k\) for \(k \ge 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 \(\mathbb{Z}_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.
ISSN:2331-8422