Hamming graph

Hamming graph
Named after	Richard Hamming
Vertices	qd
Edges	${\displaystyle {\frac {d(q-1)q^{d}}{2}}}$
Diameter	d
Spectrum	${\displaystyle \{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};}$${\displaystyle i=0,\ldots ,d\}}$
Properties	d(q − 1)-regular Vertex-transitive Distance-regular [1] Distance-balanced [2] Polytopal
Notation	H(d,q)
Table of graphs and parameters

H(3,3) drawn as a unit distance 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. ^[1]

In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes. ^[3] 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.

Special cases

• H(2,3), which is the generalized quadrangle GQ (2,1) ^[4]
• H(1,q), which is the complete graph K_q ^[5]
• H(2,q), which is the lattice graph L_q,q and also the rook's graph ^[6]
• H(d,1), which is the singleton graph K₁
• H(d,2), which is the hypercube graph Q_d. ^[1] Hamiltonian paths in these graphs form Gray codes.
• Because Cartesian products of graphs preserve the property of being a unit distance graph, ^[7] the Hamming graphs H(d,2) and H(d,3) are all unit distance graphs.

Applications

The Hamming graphs are interesting in connection with error-correcting codes ^[8] and association schemes, ^[9] to name two areas. They have also been considered as a communications network topology in distributed computing. ^[5]

Computational complexity

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. ^[3]

References

1. Brouwer, Andries E.; Haemers, Willem H. (2012), "12.3.1 Hamming graphs" (PDF), Spectra of graphs, Universitext, New York: Springer, p. 178, doi:10.1007/978-1-4614-1939-6, ISBN   978-1-4614-1938-9, MR   2882891 , retrieved 2022-08-08.
2. Karami, Hamed (2022), "Edge distance-balanced of Hamming graphs", Journal of Discrete Mathematical Sciences and Cryptography, 25: 2667–2672, doi:10.1080/09720529.2021.1914363 .
3. Imrich, Wilfried; Klavžar, Sandi (2000), "Hamming graphs", Product graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, pp. 104–106, ISBN   978-0-471-37039-0, MR   1788124 .
4. Blokhuis, Aart; Brouwer, Andries E.; Haemers, Willem H. (2007), "On 3-chromatic distance-regular graphs", Designs, Codes and Cryptography, 44 (1–3): 293–305, doi: 10.1007/s10623-007-9100-7 , MR   2336413 . See in particular note (e) on p. 300.
5. Dekker, Anthony H.; Colbert, Bernard D. (2004), "Network robustness and graph topology", Proceedings of the 27th Australasian conference on Computer science - Volume 26, ACSC '04, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 359–368.
6. Bailey, Robert F.; Cameron, Peter J. (2011), "Base size, metric dimension and other invariants of groups and graphs", Bulletin of the London Mathematical Society, 43 (2): 209–242, doi:10.1112/blms/bdq096, MR   2781204, S2CID   6684542 .
7. Horvat, Boris; Pisanski, Tomaž (2010), "Products of unit distance graphs", Discrete Mathematics , 310 (12): 1783–1792, doi: 10.1016/j.disc.2009.11.035 , MR   2610282
8. Sloane, N. J. A. (1989), "Unsolved problems in graph theory arising from the study of codes" (PDF), Graph Theory Notes of New York, 18: 11–20.
9. Koolen, Jacobus H.; Lee, Woo Sun; Martin, W (2010), "Characterizing completely regular codes from an algebraic viewpoint", Combinatorics and graphs, Contemp. Math., vol. 531, Providence, RI: Amer., pp. 223–242, arXiv: 0911.1828 , doi:10.1090/conm/531/10470, ISBN   9780821848654, MR   2757802, S2CID   8197351 . On p. 224, the authors write that "a careful study of completely regular codes in Hamming graphs is central to the study of association schemes".

External links

• Weisstein, Eric W. "Hamming Graph". MathWorld .
• Brouwer, Andries E. "Hamming graphs".