Graph Powers of Groups — Draconitic Research

Abstract

The Lights Out Puzzle, played on a graph Γ, has been studied using linear algebra over 𝔽₂ and more generally over ℤ/kℤ. We generalize the setting by allowing the states of vertices to be the elements of a group G, where a click in vertex v multiplies the state of v and its neighbors by an element g ∈ G on the right. Starting with the identity element e ∈ G for all vertices, the totality of all achievable state configurations forms a group G^Γ. This group generalizes parallel products of group actions and provides a rich structure for analysis. For many graphs, which we term "RA" (reducible to abelian), the problem reduces --- regardless of G --- to a linear algebra question over ℤ. We discuss a chain of five different subgroups consisting of commutators and introduce techniques for showing that families of graphs are RA using each. In particular, using Heisenberg groups, we establish that a graph is RA precisely when a certain lattice spans ℤ^|Γ|. While most graphs appear to be RA, we show the odd-dimensional cube graphs Q_2n+1 and folded cube graphs □_d, for d odd or 2, are not.

Clique and chromatic numbers of graph powers: spectral bounds and anticodes
Aida Abiad, Gabriel Coutinho, Hitesh Kumar +2
arXiv9 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
A Brooks-like result for graph powers $
Théo Pierron
European Journal of Combinatorics17 Sep 2026Peer-reviewedCC BY-NC 4.0Full textCombinatorics & discrete mathematicsHAL
The Zero Forcing Number of Graph Powers
Aida Abiad, Mary Flagg, Sina Ghasemi Nezhad +1
arXiv2 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
Aida Abiad, Stan van Hoesel, Valentin Michaux
arXiv17 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Linearity of Graph Manifold Groups
Daniel T. Wise
arXiv9 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Geometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@article{cunningham2026graph,
  title = {{Graph Powers of Groups}},
  author = {Gabe Cunningham and Igor Minevich},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  month = oct,
  doi = {10.37236/14315},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p16},
  note = {CC BY 4.0},
}

RIS

TY  - JOUR
TI  - Graph Powers of Groups
AU  - Gabe Cunningham
AU  - Igor Minevich
PY  - 2026
DA  - 2026/10/23
JO  - The Electronic Journal of Combinatorics
DO  - 10.37236/14315
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p16
AB  - The Lights Out Puzzle, played on a graph Γ, has been studied using linear algebra over 𝔽_2 and more generally over ℤ/kℤ. We generalize the setting by allowing the states of vertices to be the elements of a group G, where a click in vertex v multiplies the state of v and its neighbors by an element g ∈ G on the right. Starting with the identity element e ∈ G for all vertices, the totality of all achievable state configurations forms a group G^Γ. This group generalizes parallel products of group actions and provides a rich structure for analysis. For many graphs, which we term "RA" (reducible to abelian), the problem reduces --- regardless of G --- to a linear algebra question over ℤ. We discuss a chain of five different subgroups consisting of commutators and introduce techniques for showing that families of graphs are RA using each. In particular, using Heisenberg groups, we establish that a graph is RA precisely when a certain lattice spans ℤ^|Γ|. While most graphs appear to be RA, we show the odd-dimensional cube graphs Q_2n+1 and folded cube graphs □_d, for d odd or 2, are not.
SN  - 1077-8926
ER  -

Abstract

Related

Cite