Hamming graph
Template:Short description <templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox".Template:Template other
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 Template:Mvar be a set of Template:Mvar elements and Template:Mvar a positive integer. The Hamming graph H(d,q)Script error: No such module "Check for unknown parameters". has vertex set Template:Mvar, the set of ordered Template:Mvar-tuples of elements of Template:Mvar, or sequences of length Template:Mvar from Template:Mvar. 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)Script error: No such module "Check for unknown parameters". is, equivalently, the Cartesian product of Template:Mvar complete graphs Template:Mvar.[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)Script error: No such module "Check for unknown parameters"., 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)Script error: No such module "Check for unknown parameters"., which is the generalized quadrangle G Q (2,1)Script error: No such module "Check for unknown parameters".[3]
- H(1,q)Script error: No such module "Check for unknown parameters"., which is the complete graph Template:Mvar[4]
- H(2,q)Script error: No such module "Check for unknown parameters"., which is the lattice graph Template:Mvar and also the rook's graph[5]
- H(d,1)Script error: No such module "Check for unknown parameters"., which is the singleton graph K1Script error: No such module "Check for unknown parameters".
- H(d,2)Script error: No such module "Check for unknown parameters"., which is the hypercube graph Template:Mvar.[1] Hamiltonian paths in these graphs form Gray codes.
- Because Cartesian products of graphs preserve the property of being a unit distance graph,[6] the Hamming graphs H(d,2)Script error: No such module "Check for unknown parameters". and H(d,3)Script error: No such module "Check for unknown parameters". are all unit distance graphs.
Applications
The Hamming graphs are interesting in connection with error-correcting codes[7] and association schemes,[8] to name two areas. They have also been considered as a communications network topology in distributed computing.[4]
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.[2]
References
<templatestyles src="Reflist/styles.css" />
- ↑ a b Script error: No such module "citation/CS1"..
- ↑ a b Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".. See in particular note (e) on p. 300.
- ↑ a b Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".. 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".
Script error: No such module "Check for unknown parameters".
External links
- Script error: No such module "Template wrapper".
- Script error: No such module "citation/CS1".