Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

( graph theory) and computer science. Let be a set of elements and a positive integer. The Hamming graph has vertex set , the set of ordered - tuples of elements of , or sequences of length from . Two vertices are

adjacent Adjacent or adjacency may refer to: *Adjacent (graph theory), two vertices that are the endpoints of an edge in a graph *Adjacent (music), a conjunct step to a note which is next in the scale See also *Adjacent angles, two angles that share a c ...

if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph is, equivalently, the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...

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

Special cases

*, which is the generalized quadrangle *, which is the complete graph . *, which is the lattice graph and also the rook's graph *, which is the singleton graph *, which is the hypercube graph . Hamiltonian paths in these graphs form

Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representati ...

s. *Because Cartesian products of graphs preserve the property of being a unit distance graph, the Hamming graphs and are all unit distance graphs.

Applications

The Hamming graphs are interesting in connection with error-correcting codes and association schemes,. 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". to name two areas. They have also been considered as a communications network topology in distributed computing.

Computational complexity

It is possible in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

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.

References

External links

* * {{Authority control Parametric families of graphs Regular graphs