Hamming graphs are a special class of
graphsIn 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
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
and
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
. 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
adjacentIn 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 special case in which
q = 2 is also known as the
hypercube graphIn the mathematical field of graph theory, the hypercube graph Q
n is a regular graph with 2
n vertices, which correspond to the subsets of a set with n elements....
, denoted
Qd.
Discussion
Ask a question about 'Hamming graph' Start a new discussion about 'Hamming graph' Answer questions from other users |
Hamming graphs are a special class of
graphsIn 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
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
and
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
. 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
adjacentIn 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 special case in which
q = 2 is also known as the
hypercube graphIn the mathematical field of graph theory, the hypercube graph Q
n is a regular graph with 2
n vertices, which correspond to the subsets of a set with n elements....
, denoted
Qd. The special cases in which
d = 1 and
d = 2 are the
complete graphIn the mathematical field of graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on n vertices has n vertices and n/2 edges, and is denoted by . It is a regular graph of degree . All complete graphs are their own...
and
rook'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...
, respectively.
The Hamming graphs are interesting in connection with error-correcting codes and
association schemeIn mathematics, association schemes are structures that appear in many different forms in the fields of combinatorics and statistics. Their theory is one of the branches of algebraic combinatorics.-Definition:...
s, to name two areas.