Hamming graph
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 Hamming graph H(d,q) is, equivalently, the Cartesian product
of d complete graph
s Kq.
s, to name two areas.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
used in several branches of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. 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
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
if they differ in precisely one coordinate. The Hamming graph H(d,q) is, equivalently, the Cartesian product
Cartesian product of graphs
In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...
of d complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
s Kq.
Special Cases
- H(2,3), which is the generalized quadrangle G Q (2,1)
- H(1,q), which is the complete graph Kq
- H(2,q), which is the lattice graph Lq,q and also the rook's graphRook's graphIn graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move...
- H(d,1), which is the singleton graph K1
- H(d,2), which is the hypercube graph Qd
Applications
The Hamming graphs are interesting in connection with error-correcting codes and association schemeAssociation scheme
The theory of association schemes arose in statistics, in the theory of experimental design for the analysis of variance. In mathematics, association schemes belong to both algebra and combinatorics. Indeed, in algebraic combinatorics, association schemes provide a unified approach to many topics,...
s, to name two areas.