Hamming graph
{{Short description|Cartesian product of complete graphs}}
{{Infobox graph
| name = Hamming graph
| namesake = Richard Hamming
| vertices = {{mvar|q{{sup|d}}}}
| edges =
| diameter = {{mvar|d}}
| spectrum =
| properties = {{math|d(q − 1)}}-regular
Vertex-transitive
Distance-regular
10.1080/09720529.2021.1914363}}.
| notation = {{math|H(d,q)}}
}}
File:Hamming 3-3 unit distance.svg]]
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 {{mvar|S}} be a set of {{mvar|q}} elements and {{mvar|d}} a positive integer. The Hamming graph {{math|H(d,q)}} has vertex set {{mvar|S{{sup|d}}}}, the set of ordered {{mvar|d}}-tuples of elements of {{mvar|S}}, or sequences of length {{mvar|d}} from {{mvar|S}}. Two vertices are adjacent if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph {{math|H(d,q)}} is, equivalently, the Cartesian product of {{mvar|d}} complete graphs {{mvar|K{{sub|q}}}}.{{citation
| last1 = Brouwer | first1 = Andries E. | author1-link = Andries Brouwer
| last2 = Haemers | first2 = Willem H.
| doi = 10.1007/978-1-4614-1939-6
| isbn = 978-1-4614-1938-9
| location = New York
| mr = 2882891
| chapter = 12.3.1 Hamming graphs
| chapter-url = https://www.win.tue.nl/~aeb/2WF05/spectra.pdf
| access-date = 2022-08-08
| page = 178
| publisher = Springer
| series = Universitext
| title = Spectra of graphs
| year = 2012}}.
In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.{{citation
| last1 = Imrich | first1 = Wilfried
| last2 = Klavžar | first2 = Sandi | author2-link = Sandi Klavžar
| contribution = Hamming graphs
| isbn = 978-0-471-37039-0
| mr = 1788124
| pages = 104–106
| publisher = Wiley-Interscience, New York
| series = Wiley-Interscience Series in Discrete Mathematics and Optimization
| title = Product graphs
| year = 2000}}. Unlike the Hamming graphs {{math|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
- {{math|H(2,3)}}, which is the generalized quadrangle {{math|G Q (2,1)}}{{citation
| last1 = Blokhuis | first1 = Aart
| last2 = Brouwer | first2 = Andries E. | author2-link = Andries Brouwer
| last3 = Haemers | first3 = Willem H.
| doi = 10.1007/s10623-007-9100-7
| issue = 1–3
| journal = Designs, Codes and Cryptography
| mr = 2336413
| pages = 293–305
| title = On 3-chromatic distance-regular graphs
| volume = 44
| year = 2007| doi-access = free
}}. See in particular note (e) on p. 300.
- {{math|H(1,q)}}, which is the complete graph {{mvar|K{{sub|q}}}}{{citation
| last1 = Dekker | first1 = Anthony H.
| last2 = Colbert | first2 = Bernard D.
| contribution = Network robustness and graph topology
| location = Darlinghurst, Australia, Australia
| pages = 359–368
| publisher = Australian Computer Society, Inc.
| series = ACSC '04
| title = Proceedings of the 27th Australasian conference on Computer science - Volume 26
| url = http://dl.acm.org/citation.cfm?id=979922.979965
| year = 2004}}.
- {{math|H(2,q)}}, which is the lattice graph {{mvar|L{{sub|q,q}}}} and also the rook's graph{{citation
| last1 = Bailey | first1 = Robert F.
| last2 = Cameron | first2 = Peter J.
| doi = 10.1112/blms/bdq096
| issue = 2
| journal = Bulletin of the London Mathematical Society
| mr = 2781204
| pages = 209–242
| title = Base size, metric dimension and other invariants of groups and graphs
| volume = 43
| year = 2011| s2cid = 6684542
}}.
- {{math|H(d,1)}}, which is the singleton graph {{math|K{{sub|1}}}}
- {{math|H(d,2)}}, which is the hypercube graph {{mvar|Q{{sub|d}}}}. Hamiltonian paths in these graphs form Gray codes.
- Because Cartesian products of graphs preserve the property of being a unit distance graph,{{citation
| last1 = Horvat | first1 = Boris
| last2 = Pisanski | first2 = Tomaž | author2-link = Tomaž Pisanski
| doi = 10.1016/j.disc.2009.11.035
| issue = 12
| journal = Discrete Mathematics
| mr = 2610282
| pages = 1783–1792
| title = Products of unit distance graphs
| volume = 310
| year = 2010| doi-access = free
}} the Hamming graphs {{math|H(d,2)}} and {{math|H(d,3)}} are all unit distance graphs.
Applications
The Hamming graphs are interesting in connection with error-correcting codes{{citation
| last = Sloane | first = N. J. A. | author-link = Neil Sloane
| journal = Graph Theory Notes of New York
| pages = 11–20
| title = Unsolved problems in graph theory arising from the study of codes
| url = http://neilsloane.com/doc/pace2.pdf
| volume = 18
| year = 1989}}. and association schemes,{{citation
| last1 = Koolen | first1 = Jacobus H.
| last2 = Lee | first2 = Woo Sun
| last3 = Martin | first3= W
| contribution = Characterizing completely regular codes from an algebraic viewpoint
| doi = 10.1090/conm/531/10470
| location = Providence, RI
| mr = 2757802
| pages = 223–242
| publisher = Amer.
| series = Contemp. Math.
| title = Combinatorics and graphs
| volume = 531
| year = 2010| arxiv = 0911.1828
| isbn = 9780821848654
| 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". to name two areas. They have also been considered as a communications network topology in distributed computing.
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.
References
{{Reflist}}
External links
- {{MathWorld | title = Hamming Graph | id = HammingGraph}}
- {{cite web
| url = http://www.win.tue.nl/~aeb/graphs/Hamming.html
| title = Hamming graphs
| first = Andries E.
| last = Brouwer
| authorlink = Andries E. Brouwer
}}
{{Authority control}}