TOPICS
Search

Hamming Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HammingGraphs

The Hamming graph H(d,q), sometimes also denoted q^d, is the graph Cartesian product of d copies of the complete graph K_q. H(d,q) therefore has q^d vertices.

H(d,q) has chromatic number q (S. Wagon, pers. comm., Feb. 16, 2013) and graph diameter d. Hammin graphs are distance-regular and geomtric (Koolen et al. 2023).

Special cases are summarized in the following table.

H(1,q)complete graph K_q
H(2,3)generalized quadrangle GQ(2,1)
H(2,q)rook graph L_(q,q)
H(d,1)singleton graph K_1
H(d,2)hypercube graph Q_d

The Doob graph D(m,n) is the graph given by the graph Cartesian product of m>=1 copies of the Shrikhande graph with a Hamming graph H(n,4). H(n+2m,4) is cospectral with the Doob graph D(m,n) and shares the same regularity parameters.

Hamming33Embeddings

Some order-3 LCF notations of H(3,3) are illustrated above.

Hamming33UnitDistance

Because the graph Cartesian product of unit-distance graphs are themselves unit-distance, the Hamming graphs H(d,2) and H(d,3) are unit-distance. A (degenerate) unit-distance embedding of H(3,3) is shown above (E. Gerbracht, pers. comm., May 2008).

See also

Complete Graph, Doob Graph, Egawa Graph Hamming Code, Hamming Distance, Hypercube Graph, Rook Graph, xyz Embedding

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Hamming Graphs." http://www.win.tue.nl/~aeb/drg/graphs/Hamming.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Hamming Graphs." §9.2 in Distance-Regular Graphs. New York: Springer-Verlag, pp. 261-267, 1989.DistanceRegular.org. "Hamming Graphs H(d,q)." http://www.distanceregular.org/indexes/hamminggraphs.html.Haemers, W. H. "Distance-Regularity and the Spectrum of Graphs." Linear Alg. Appl. 236, 265-278, 1996.Haemers, W. H. and Spence, E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin. Alg. 39, 91-107, 1995.Koolen, J. H.; Yu, K.; Liang, X.; Choi, H.; and Markowsky, G. "Non-Geometric Distance-Regular Graphs of Diameter at Least 3 With Smallest Eigenvalue at Least -3." 15 Nov 2023. https://arxiv.org/abs/2311.09001.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.Mulder, H. M. The Interval Function of a Graph. Amsterdam, Netherlands: Mathematisch Centrum, 1980.

Referenced on Wolfram|Alpha

Hamming Graph

Cite this as:

Weisstein, Eric W. "Hamming Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HammingGraph.html

Subject classifications