Hamming graph
Page Template:Infobox graph/styles.css has no content.Page Module:Infobox/styles.css has no content.
| Hamming graph | |
|---|---|
| Named after | Richard Hamming |
| Vertices | qd |
| Edges | |
| Diameter | d |
| Spectrum | |
| Properties | d(q − 1)-regular Vertex-transitive Distance-regular[1] Distance-balanced[2] Polytopal |
| 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
Page Template:Reflist/styles.css has no content.
- ^ a b c Page Module:Citation/CS1/styles.css has no content.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.
- ^ Page Module:Citation/CS1/styles.css has no content.Karami, Hamed (2022), "Edge distance-balanced of Hamming graphs", Journal of Discrete Mathematical Sciences and Cryptography, 25 (8): 2667–2672, doi:10.1080/09720529.2021.1914363.
- ^ a b Page Module:Citation/CS1/styles.css has no content.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.
- ^ Page Module:Citation/CS1/styles.css has no content.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.
- ^ a b Page Module:Citation/CS1/styles.css has no content.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, vol. 26, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 359–368.
- ^ Page Module:Citation/CS1/styles.css has no content.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.
- ^ Page Module:Citation/CS1/styles.css has no content.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
- ^ Page Module:Citation/CS1/styles.css has no content.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.
- ^ Page Module:Citation/CS1/styles.css has no content.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
- Script error: No such module "Template wrapper".
- Page Module:Citation/CS1/styles.css has no content.Brouwer, Andries E. "Hamming graphs".
Lua error in package.lua at line 80: module 'Module:Authority control/config' not found.
