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).

H(3,3) has graph genus 7 (Conder and Stokes 2019, Brinkmann 2020).

See also

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

Explore with Wolfram|Alpha

References

Brinkmann, G. "A Practical Algorithm for the Computation of the Genus." 17 May 2020. https://arxiv.org/abs/2005.08243.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.Conder, M. and Stokes, K. "New Methods for Finding Minimum Genus Embeddings of Graphs on Orientable and Non-Orientable Surfaces." Ars. Math. Contemp. 17, 1-35, 2019.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 Resource. https://mathworld.wolfram.com/HammingGraph.html

Subject classifications