# Hamming graph

Template:Infobox graph
**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}.

^{[1]}

In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.^{[2]} 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)^{[3]}*H*(1,*q*), which is the complete graph*K*_{q}^{[4]}*H*(2,*q*), which is the lattice graph*L*_{q,q}and also the rook's graph^{[5]}*H*(*d*,1), which is the singleton graph*K*_{1}*H*(*d*,2), which is the hypercube graph*Q*_{d}^{[1]}

## Applications

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

## Computational complexity

It is possible 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, in linear time.^{[2]}

## References

- ↑
^{1.0}^{1.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑
^{2.0}^{2.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}. See in particular note (e) on p. 300.
- ↑
^{4.0}^{4.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}. On p. 224, the authors write that "a careful study of completely regular codes in Hamming graphs is central to the study of association schemes".