An exact-distance Hamming graph is the graph on words
of length
over an alphabet of
symbols in which two words are adjacent precisely when their Hamming
distance is
,
where
,
,
and
are integers with
,
, and
.
It is the graph distance graph at distance
of the Hamming graph
. In particular,
, whereas larger exact distances generally
give different graphs (Brešar et al. 2019).
Each graph vertex has vertex
degree
,
by choosing the positions that change and one of
replacement symbols at each position.
Let
be the largest number of vertices whose induced
subgraph is a triangle-free graph. Csajbók
et al. (2026) proved that
and
for every fixed integer
. They also determined the exact order in the
ternary distance-four case,
where
is big-Theta notation and the constants
implicit in
may depend on
.
The asymptotic estimates are for
.