{
  "id": "2306.06017",
  "version": "v1",
  "published": "2023-06-09T16:36:40.000Z",
  "updated": "2023-06-09T16:36:40.000Z",
  "title": "The Lights Out Game on Directed Graphs",
  "authors": [
    "T. Elise Dettling",
    "Darren B. Parker"
  ],
  "categories": [
    "math.CO"
  ],
  "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 $\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-06-09T16:36:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C50",
      "05C57",
      "05C78",
      "05C40"
    ],
    "keywords": [
      "directed graphs",
      "minimum feedback arc set",
      "directed star digraph",
      "determine winnability",
      "acyclic digraphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}