Hamming graph

From formulasearchengine
Jump to navigation Jump to search

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 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; that is, if their Hamming distance is one. The Hamming graph H(d,q) is, equivalently, the Cartesian product of d complete graphs Kq.[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 Kq[4]
  • H(2,q), which is the lattice graph Lq,q and also the rook's graph[5]
  • H(d,1), which is the singleton graph K1
  • H(d,2), which is the hypercube graph Qd[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. 1.0 1.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  2. 2.0 2.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  3. {{#invoke:citation/CS1|citation |CitationClass=citation }}. See in particular note (e) on p. 300.
  4. 4.0 4.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  5. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  6. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  7. {{#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".

External links