Hamming graph

Hamming graph
Named after	Richard Hamming
Vertices	$q^d$
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^[1]
Notation	H $(d,q)$

Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics 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^d, 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_q.^[1]

In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.^[2] 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)^[3]
H(1,q), which is the complete graph K_q^[4]
H(2,q), which is the lattice graph L_q,q and also the rook's graph^[5]
H(d,1), which is the singleton graph K₁
H(d,2), which is the hypercube graph Q_d^[1]

Applications

The Hamming graphs are interesting in connection with error-correcting codes^[6] and association schemes,^[7] to name two areas. They have also been considered as a communications network topology in distributed computing.^[4]

Computational complexity

It is possible 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, in linear time.^[2]

References

1 2 3 Brouwer, Andries E.; Haemers, Willem H. (2012), 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 .
1 2 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 0-471-37039-8, MR 1788124 .
↑ 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.
1 2 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, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 359–368 .
↑ 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 .
↑ 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 .
↑ Koolen, Jacobus H.; Lee, Woo Sun; Martin, William J. (2010), "Characterizing completely regular codes from an algebraic viewpoint", Combinatorics and graphs, Contemp. Math. 531, Providence, RI: Amer. Math. Soc., pp. 223–242, doi:10.1090/conm/531/10470, MR 2757802 . 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

This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.