Hamming graph

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

Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics 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.

Special Cases

• H(2,3), which is the generalized quadrangle G Q (2,1)
• H(1,q), which is the complete graph K_q
• H(2,q), which is the lattice graph L_q,q and also the rook's graph
• H(d,1), which is the singleton graph K₁
• H(d,2), which is the hypercube graph Q_d

Applications

The Hamming graphs are interesting in connection with error-correcting codes and association schemes, to name two areas.

References

• Weisstein, Eric W. "Hamming Graph". From MathWorld--A Wolfram Web Resource.
• Brouwer, Andries E. "Hamming graphs".