View source for Hamming graph

{{Short description|Cartesian product of complete graphs}}
{{Infobox graph
 | name = Hamming graph
 | namesake = [[Richard Hamming]]
 | vertices = {{mvar|q{{sup|d}}}}
 | edges = <math> \frac{d(q-1)q^d}{2}</math>
 | diameter = {{mvar|d}}
 | spectrum = <math>\{(d (q - 1) - q i)^{\binom{d}{i} (q - 1)^i};</math><math>i = 0, \ldots, d\}</math>
 | properties = {{math|''d''(''q'' – 1)}}-[[Regular graph|regular]]<br/>[[Vertex-transitive graph|Vertex-transitive]]<br/>[[Distance-regular graph|Distance-regular]]<ref name="bh12"/>
Distance-balanced<ref>{{citation | last = Karami| first = Hamed | journal = Journal of Discrete Mathematical Sciences and Cryptography | title = Edge distance-balanced of Hamming graphs | volume = 25 | pages = 2667-2672 | year = 2022 | doi =  
 10.1080/09720529.2021.1914363}}.</ref>
 | notation = {{math|''H''(''d'',''q'')}} 
}}
[[File:Hamming 3-3 unit distance.svg|thumb|{{math|''H''(3,3)}} drawn as a [[unit distance graph]]]]

'''Hamming graphs''' are a special class of [[Graph (discrete mathematics)|graphs]] named after [[Richard Hamming]] and used in several branches of [[mathematics]] ([[graph theory]]) and [[computer science]].  Let {{mvar|S}} be a [[Set (mathematics)|set]] of {{mvar|q}} elements and {{mvar|d}} a positive [[integer]].  The Hamming graph {{math|''H''(''d'',''q'')}} has [[Vertex (graph theory)|vertex]] set {{mvar|S{{sup|d}}}}, the set of ordered {{mvar|d}}-[[tuple]]s of elements of {{mvar|S}}, or sequences of length {{mvar|d}} from {{mvar|S}}.  Two vertices are [[graph (discrete mathematics)|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 graphs|Cartesian product]] of {{mvar|d}} [[complete graph]]s {{mvar|K{{sub|q}}}}.<ref name="bh12">{{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}}.</ref>

In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.<ref name="ik00">{{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}}.</ref> Unlike the Hamming graphs {{math|''H''(''d'',''q'')}}, the graphs in this more general class are not necessarily [[distance-regular graph|distance-regular]], but they continue to be [[regular graph|regular]] and [[vertex-transitive graph|vertex-transitive]].

==Special cases==

*{{math|''H''(2,3)}}, which is the generalized [[Complete quadrangle|quadrangle]] {{math|''G'' ''Q'' (2,1)}}<ref>{{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.&nbsp;300.</ref>
*{{math|''H''(1,''q'')}}, which is the complete graph {{mvar|K{{sub|q}}}}<ref name="dc04">{{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}}.</ref>
*{{math|''H''(2,''q'')}}, which is the [[lattice graph]] {{mvar|L{{sub|q,q}}}} and also the [[rook's graph]]<ref>{{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
 }}.</ref>
*{{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}}}}.<ref name="bh12"/> [[Hamiltonian path]]s in these graphs form [[Gray code]]s.
*Because [[Cartesian product of graphs|Cartesian products of graphs]] preserve the property of being a [[unit distance graph]],<ref>{{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 (journal)|Discrete Mathematics]]
 | mr = 2610282
 | pages = 1783–1792
 | title = Products of unit distance graphs
 | volume = 310
 | year = 2010| doi-access = free
 }}</ref> 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]]<ref>{{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}}.</ref> and [[association scheme]]s,<ref>{{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".</ref> to name two areas. They have also been considered as a communications network topology in [[distributed computing]].<ref name="dc04"/>

==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.<ref name="ik00"/>

==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}}

[[Category:Parametric families of graphs]]
[[Category:Regular graphs]]