Hamming graph

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 S^d, 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 K_q. 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 H(d,q), the graphs in this more general class are not necessarily distance-regular, but they continue to be regular and vertex-transitive. H(2,3), which is the generalized quadrangle G Q (2,1) H(1,q), which is the complete graph K_q H(2,q), which is the lattice graph L_q,q and also the rook's graph H(d,1), which is the singleton graph K_1 H(d,2), which is the hypercube graph Q_d. 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 H(d,2) and H(d,3) are all unit distance graphs. 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. 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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (4)

Hypercube graph

In graph theory, the hypercube graph Q_n is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^n – 1n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n may also be constructed by creating a vertex for each subset of an n-element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n-digit binary number, with two vertices adjacent when their binary representations differ in a single digit.

Hamming graph

Cartesian product of graphs

In graph theory, the Cartesian product G □ H of graphs G and H is a graph such that: the vertex set of G □ H is the Cartesian product V(G) × V(H); and two vertices (u,u' ) and (v,v' ) are adjacent in G □ H if and only if either u = v and u' is adjacent to v' in H, or u' = v' and u is adjacent to v in G. The Cartesian product of graphs is sometimes called the box product of graphs [Harary 1969]. The operation is associative, as the graphs (F □ G) □ H and F □ (G □ H) are naturally isomorphic.