Hamming graph

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.^[1]

Hamming graph
Named after	Richard Hamming
Vertices	qd
Edges	${\displaystyle {\frac {d(q-1)q^{d}}{2}}}$
Diameter	d
Spectrum	${\displaystyle \{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};}$${\displaystyle i=0,\ldots ,d\}}$
Properties	d(q – 1)-regular Vertex-transitive Distance-regular[1] Distance-balanced[2]
Notation	H(d,q)
Table of graphs and parameters

H(3,3) drawn as a unit distance graph

In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.^[3] Unlike the Hamming graphs H(d,q), the graphs in this more general class are not necessarily distance-regular, but they continue to be regular and vertex-transitive.

Special cases

• H(2,3), which is the generalized quadrangle G Q (2,1)^[4]
• H(1,q), which is the complete graph K_q^[5]
• H(2,q), which is the lattice graph L_q,q and also the rook's graph^[6]
• H(d,1), which is the singleton graph K₁
• H(d,2), which is the hypercube graph Q_d.^[1] Hamiltonian paths in these graphs form Gray codes.
• Because Cartesian products of graphs preserve the property of being a unit distance graph,^[7] the Hamming graphs H(d,2) and H(d,3) are all unit distance graphs.

Applications

The Hamming graphs are interesting in connection with error-correcting codes^[8] and association schemes,^[9] to name two areas. They have also been considered as a communications network topology in distributed computing.^[5]

Computational complexity

It is possible in linear time to test whether a graph is a Hamming graph, and in the case that it is, find a labeling of it with tuples that realizes it as a Hamming graph.^[3]