Hamming graph
| Hamming graph | |
|---|---|
| Named after | Richard Hamming |
| Vertices | qd |
| Edges | [math]\displaystyle{ \frac{d(q-1)q^d}{2} }[/math] |
| Diameter | d |
| Spectrum | [math]\displaystyle{ \{(d (q - 1) - q i)^{\binom{d}{i} (q - 1)^i}; }[/math][math]\displaystyle{ i = 0, \ldots, d\} }[/math] |
| Properties | d(q – 1)-regular Vertex-transitive Distance-regular[1] Distance-balanced[2] |
| Notation | H(d,q) |
| Table of graphs and parameters | |
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 Sd, 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 Kq.[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 G Q (2,1)[4]
- H(1,q), which is the complete graph Kq[5]
- H(2,q), which is the lattice graph Lq,q and also the rook's graph[6]
- H(d,1), which is the singleton graph K1
- H(d,2), which is the hypercube graph Qd.[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.0 1.1 1.2 "12.3.1 Hamming graphs", Spectra of graphs, Universitext, New York: Springer, 2012, p. 178, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, https://www.win.tue.nl/~aeb/2WF05/spectra.pdf, retrieved 2022-08-08.
- ↑ 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.0 3.1 Imrich, Wilfried (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.
- ↑ Blokhuis, Aart (2007), "On 3-chromatic distance-regular graphs", Designs, Codes and Cryptography 44 (1–3): 293–305, doi:10.1007/s10623-007-9100-7. See in particular note (e) on p. 300.
- ↑ 5.0 5.1 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, http://dl.acm.org/citation.cfm?id=979922.979965.
- ↑ 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.
- ↑ Horvat, Boris (2010), "Products of unit distance graphs", Discrete Mathematics 310 (12): 1783–1792, doi:10.1016/j.disc.2009.11.035
- ↑ "Unsolved problems in graph theory arising from the study of codes", Graph Theory Notes of New York 18: 11–20, 1989, http://neilsloane.com/doc/pace2.pdf.
- ↑ Koolen, Jacobus H.; Lee, Woo Sun; Martin, W (2010), "Characterizing completely regular codes from an algebraic viewpoint", Combinatorics and graphs, Contemp. Math., 531, Providence, RI: Amer., pp. 223–242, doi:10.1090/conm/531/10470, ISBN 9780821848654. 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". http://mathworld.wolfram.com/HammingGraph.html.
- Brouwer, Andries E.. "Hamming graphs". http://www.win.tue.nl/~aeb/graphs/Hamming.html.
 |  |
