A generalized Keller graph has as its vertices the n-tuples over the integers
0, 1, ..., . Two vertices are
adjacent if they differ by exactly
in at least one coordinate and differ in at least two coordinates
(Brakensiek et al. 2022). By definition, it is a Cayley
graph of the additive group
whose connection set
consists of the vectors having at least one coordinate
equal to
and at least two nonzero coordinates. This set is inverse-closed
because taking additive inverses modulo
preserves both properties.
The generalized Keller graph with parameters and
is denoted
,
or
after the notation
of Łysakowska (2023). Its vertex set therefore has
elements. The ordinary
-dimensional Keller graph
is the special case
.
Special cases, including the natural boundary cases with or
,
are summarized in the following table.
| graph | |
| ladder rung graph | |
| Clebsch graph | |
For , generalized Keller graphs are vertex-transitive
and regular, with vertex
degree
. Their chromatic
number is
, and their independence
number is
for
. In addition, Łysakowska (2023) proved that
all generalized Keller graphs are Hamiltonian
and class 1.
Corrádi and Szabó (1990) introduced the graphs
to give a convenient finite graph-theoretic formulation
of Keller's conjecture, translating the search
for face-sharing-free periodic hypercube tilings
into a clique problem. A clique
in
has size at most
,
and one attaining this bound gives a face-sharing-free tiling
of
-dimensional
space. It therefore disproves Keller's conjecture
in dimension
and all higher dimensions. Łysakowska (2023) later used the term generalized
Keller graph for the family and studied its graph-theoretic properties.
For the remaining seven-dimensional case, Brakensiek et al. (2022) encoded the clique search as a satisfiability problem
and used symmetry breaking to prove that none of ,
,
and
contains a clique of size 128. This settled Keller's
conjecture by proving it in dimension seven.
Generalized Keller graphs are implemented in the Wolfram Language as GraphData[{"GeneralizedKeller", {n, s}}].