# Hamming graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Hamming_graph
> Markdown URL: https://mediated.wiki/source/Hamming_graph.md
> Source: https://en.wikipedia.org/wiki/Hamming_graph
> Source revision: 1317745629
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Cartesian product of complete graphs

Hamming graph Named after Richard Hamming Vertices qd Edges d ( q − 1 ) q d 2 {\displaystyle {\frac {d(q-1)q^{d}}{2}}} Diameter d Spectrum { ( d ( q − 1 ) − q i ) ( d i ) ( q − 1 ) i ; {\displaystyle \{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};} i = 0 , … , d } {\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](/source/Unit_distance_graph)

**Hamming graphs** are a special class of [graphs](/source/Graph_(discrete_mathematics)) named after [Richard Hamming](/source/Richard_Hamming) and used in several branches of [mathematics](/source/Mathematics) ([graph theory](/source/Graph_theory)) and [computer science](/source/Computer_science). Let S be a [set](/source/Set_(mathematics)) of q elements and d a positive [integer](/source/Integer). The Hamming graph *H*(*d*,*q*) has [vertex](/source/Vertex_(graph_theory)) set Sd, the set of ordered d-[tuples](/source/Tuple) of elements of S, or sequences of length d from S. Two vertices are [adjacent](/source/Graph_(discrete_mathematics)) if they differ in precisely one coordinate; that is, if their [Hamming distance](/source/Hamming_distance) is one. The Hamming graph *H*(*d*,*q*) is, equivalently, the [Cartesian product](/source/Cartesian_product_of_graphs) of d [complete graphs](/source/Complete_graph) 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](/source/Distance-regular_graph), but they continue to be [regular](/source/Regular_graph) and [vertex-transitive](/source/Vertex-transitive_graph).

## Special cases

- *H*(2,3), which is the generalized [quadrangle](/source/Complete_quadrangle) *G* *Q* (2,1)[4]

- *H*(1,*q*), which is the complete graph Kq[5]

- *H*(2,*q*), which is the [lattice graph](/source/Lattice_graph) Lq,q and also the [rook's graph](/source/Rook's_graph)[6]

- *H*(*d*,1), which is the singleton graph *K*1

- *H*(*d*,2), which is the [hypercube graph](/source/Hypercube_graph) Qd.[1] [Hamiltonian paths](/source/Hamiltonian_path) in these graphs form [Gray codes](/source/Gray_code).

- Because [Cartesian products of graphs](/source/Cartesian_product_of_graphs) preserve the property of being a [unit distance graph](/source/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](/source/Error-correcting_codes)[8] and [association schemes](/source/Association_scheme),[9] to name two areas. They have also been considered as a communications network topology in [distributed computing](/source/Distributed_computing).[5]

## Computational complexity

It is possible in [linear time](/source/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. ^ [***a***](#cite_ref-bh12_1-0) [***b***](#cite_ref-bh12_1-1) [***c***](#cite_ref-bh12_1-2) [Brouwer, Andries E.](/source/Andries_Brouwer); Haemers, Willem H. (2012), ["12.3.1 Hamming graphs"](https://www.win.tue.nl/~aeb/2WF05/spectra.pdf) (PDF), *Spectra of graphs*, Universitext, New York: Springer, p. 178, [doi](/source/Doi_(identifier)):[10.1007/978-1-4614-1939-6](https://doi.org/10.1007%2F978-1-4614-1939-6), [ISBN](/source/ISBN_(identifier)) [978-1-4614-1938-9](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4614-1938-9), [MR](/source/MR_(identifier)) [2882891](https://mathscinet.ams.org/mathscinet-getitem?mr=2882891), retrieved 2022-08-08.

1. **[^](#cite_ref-2)** Karami, Hamed (2022), "Edge distance-balanced of Hamming graphs", *Journal of Discrete Mathematical Sciences and Cryptography*, **25** (8): 2667–2672, [doi](/source/Doi_(identifier)):[10.1080/09720529.2021.1914363](https://doi.org/10.1080%2F09720529.2021.1914363).

1. ^ [***a***](#cite_ref-ik00_3-0) [***b***](#cite_ref-ik00_3-1) Imrich, Wilfried; [Klavžar, Sandi](/source/Sandi_Klav%C5%BEar) (2000), "Hamming graphs", *Product graphs*, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, pp. 104–106, [ISBN](/source/ISBN_(identifier)) [978-0-471-37039-0](https://en.wikipedia.org/wiki/Special:BookSources/978-0-471-37039-0), [MR](/source/MR_(identifier)) [1788124](https://mathscinet.ams.org/mathscinet-getitem?mr=1788124).

1. **[^](#cite_ref-4)** Blokhuis, Aart; [Brouwer, Andries E.](/source/Andries_Brouwer); Haemers, Willem H. (2007), "On 3-chromatic distance-regular graphs", *Designs, Codes and Cryptography*, **44** (1–3): 293–305, [doi](/source/Doi_(identifier)):[10.1007/s10623-007-9100-7](https://doi.org/10.1007%2Fs10623-007-9100-7), [MR](/source/MR_(identifier)) [2336413](https://mathscinet.ams.org/mathscinet-getitem?mr=2336413). See in particular note (e) on p. 300.

1. ^ [***a***](#cite_ref-dc04_5-0) [***b***](#cite_ref-dc04_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*](http://dl.acm.org/citation.cfm?id=979922.979965), ACSC '04, vol. 26, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 359–368.

1. **[^](#cite_ref-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](/source/Doi_(identifier)):[10.1112/blms/bdq096](https://doi.org/10.1112%2Fblms%2Fbdq096), [MR](/source/MR_(identifier)) [2781204](https://mathscinet.ams.org/mathscinet-getitem?mr=2781204), [S2CID](/source/S2CID_(identifier)) [6684542](https://api.semanticscholar.org/CorpusID:6684542).

1. **[^](#cite_ref-7)** Horvat, Boris; [Pisanski, Tomaž](/source/Toma%C5%BE_Pisanski) (2010), "Products of unit distance graphs", *[Discrete Mathematics](/source/Discrete_Mathematics_(journal))*, **310** (12): 1783–1792, [doi](/source/Doi_(identifier)):[10.1016/j.disc.2009.11.035](https://doi.org/10.1016%2Fj.disc.2009.11.035), [MR](/source/MR_(identifier)) [2610282](https://mathscinet.ams.org/mathscinet-getitem?mr=2610282)

1. **[^](#cite_ref-8)** [Sloane, N. J. A.](/source/Neil_Sloane) (1989), ["Unsolved problems in graph theory arising from the study of codes"](http://neilsloane.com/doc/pace2.pdf) (PDF), *Graph Theory Notes of New York*, **18**: 11–20.

1. **[^](#cite_ref-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](/source/ArXiv_(identifier)):[0911.1828](https://arxiv.org/abs/0911.1828), [doi](/source/Doi_(identifier)):[10.1090/conm/531/10470](https://doi.org/10.1090%2Fconm%2F531%2F10470), [ISBN](/source/ISBN_(identifier)) [9780821848654](https://en.wikipedia.org/wiki/Special:BookSources/9780821848654), [MR](/source/MR_(identifier)) [2757802](https://mathscinet.ams.org/mathscinet-getitem?mr=2757802), [S2CID](/source/S2CID_(identifier)) [8197351](https://api.semanticscholar.org/CorpusID: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.](/source/Eric_W._Weisstein) ["Hamming Graph"](https://mathworld.wolfram.com/HammingGraph.html). *[MathWorld](/source/MathWorld)*.

- [Brouwer, Andries E.](/source/Andries_E._Brouwer) ["Hamming graphs"](http://www.win.tue.nl/~aeb/graphs/Hamming.html).

Authority control databases GND

---
Adapted from the Wikipedia article [Hamming graph](https://en.wikipedia.org/wiki/Hamming_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Hamming_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.