Hamming graph

Summary

Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science. Let $S$ be a set of $q$ elements and $d$ a positive integer. The Hamming graph $H(d,q)$ has vertex set $S^{d}$, the set of ordered $d$-tuples of elements of $S$, or sequences of length $d$ from $S$. Two vertices are adjacent if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph $H(d,q)$ is, equivalently, the Cartesian product of $d$ complete graphs $K_{q}$.