A generalized Keller graph has as its vertices the 
-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).
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 |
 |  -empty graph |
 | ladder rung graph  |
 | Clebsch graph |
 |  rook graph |
 |  -dimensional Keller 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 cube 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 will be implemented in a future version of the Wolfram Language as GraphData[
"GeneralizedKeller",
n,
s
].
