Hamming graph

{{Infobox graph | name = Hamming graph | namesake = Richard Hamming | vertices = | edges = \frac{d(q-1)q^d}{2} | diameter = | spectrum = \{(d (q - 1) - q i)^{\binom{d}{i} (q - 1)^i}; i = 0, \ldots, d\} | properties = -regular Vertex-transitive Distance-regular Distance-balanced Polytopal | notation = }} Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of 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 if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph is, equivalently, the Cartesian product 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.

{{Infobox graph | name = Hamming graph | namesake = Richard Hamming | vertices = | edges = \frac{d(q-1)q^d}{2} | diameter = | spectrum = \{(d (q - 1) - q i)^{\binom{d}{i} (q - 1)^i}; i = 0, \ldots, d\} | properties = -regular Vertex-transitive Distance-regular Distance-balanced Polytopal | notation = }} ]] Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of 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 if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph is, equivalently, the Cartesian product 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 codes. 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, 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 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==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1317745629 under CC BY-SA 4.0; modifications have been made.