Hamming graph

From Wikipedia, the free encyclopedia

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 Sd, 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 special case in which q = 2 is also known as the hypercube graph, denoted Qd. The special cases in which d = 1 and d = 2 are the complete graph and rook's graph, respectively.

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

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.