Hamming graph

Hamming graph
Named after	Richard Hamming
Vertices	qd
Edges	${\frac {q^{d+1}}{2}}$
Diameter	d
Properties	q-regular Vertex-transitive
Notation	H(d,q)
Table of graphs and parameters

Hamming graphs are a special class of graphs 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. 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.