Hamming graph
Cartesian product of complete graphs
title: "Hamming graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["parametric-families-of-graphs", "regular-graphs"] description: "Cartesian product of complete graphs" topic_path: "general/parametric-families-of-graphs" source: "https://en.wikipedia.org/wiki/Hamming_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Cartesian product of complete graphs ::
::data[format=table title="Infobox graph"]
| Field | Value |
|---|---|
| name | Hamming graph |
| namesake | Richard Hamming |
| vertices | q |
| edges | \frac{d(q-1)q^d}{2} |
| diameter | d |
| spectrum | {(d (q - 1) - q i)^{\binom{d}{i} (q - 1)^i};i = 0, \ldots, d} |
| properties | d(q − 1)-regular |
| Vertex-transitive | |
| Distance-regular | |
Distance-balanced{{citation | last |
| notation | H(d,q) |
| :: |
| name = Hamming graph | namesake = Richard Hamming | vertices = q | edges = \frac{d(q-1)q^d}{2} | diameter = d | spectrum = {(d (q - 1) - q i)^{\binom{d}{i} (q - 1)^i};i = 0, \ldots, d} | properties = d(q − 1)-regular Vertex-transitive Distance-regular
Distance-balanced{{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 | issue = 8 | doi = 10.1080/09720529.2021.1914363}}. Polytopal | notation = H(d,q) ::figure[src="https://upload.wikimedia.org/wikipedia/commons/0/06/Hamming_3-3_unit_distance.svg" caption="''H''(3,3)}} drawn as a [[unit distance graph"] ::
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 S, 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 K.{{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 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){{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
- H(1,q), which is the complete graph K{{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 | volume = 26
- H(2,q), which is the lattice graph L 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
- H(d,1), which is the singleton graph K
- H(d,2), which is the hypercube graph Q. 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
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
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
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::