The Lights Out Game on Directed Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914304162267136 |
|---|---|
| author | Dettling, T. Elise Parker, Darren B. |
| author_facet | Dettling, T. Elise Parker, Darren B. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_06017 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Lights Out Game on Directed Graphs Dettling, T. Elise Parker, Darren B. Combinatorics 05C20 (Primary), 05C50 (Primary), 05C57 (Primary), 05C78 (Primary), 05C40 (Secondary) 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. |
| title | The Lights Out Game on Directed Graphs |
| topic | Combinatorics 05C20 (Primary), 05C50 (Primary), 05C57 (Primary), 05C78 (Primary), 05C40 (Secondary) |
| url | https://arxiv.org/abs/2306.06017 |