Hamming graph | |
---|---|
Named after | Richard Hamming |
Vertices | qd |
Edges | |
Diameter | d |
Spectrum | |
Properties | d(q – 1)-
regular Vertex-transitive Distance-regular [1] Distance-balanced [2] |
Notation | H(d,q) |
Table of graphs and parameters |
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 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. [3] 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.
The Hamming graphs are interesting in connection with error-correcting codes [8] and association schemes, [9] to name two areas. They have also been considered as a communications network topology in distributed computing. [5]
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. [3]
Hamming graph | |
---|---|
Named after | Richard Hamming |
Vertices | qd |
Edges | |
Diameter | d |
Spectrum | |
Properties | d(q – 1)-
regular Vertex-transitive Distance-regular [1] Distance-balanced [2] |
Notation | H(d,q) |
Table of graphs and parameters |
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 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. [3] 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.
The Hamming graphs are interesting in connection with error-correcting codes [8] and association schemes, [9] to name two areas. They have also been considered as a communications network topology in distributed computing. [5]
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. [3]