Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Hamming graph
open-in-new
<p>Hamming graphs are a special class of <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a> named after <a href="/facts/Richard_Hamming/plAXy9p0">Richard Hamming</a> and used in several branches of <a href="/facts/Mathematics/pxTouaz4">mathematics</a> (<a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>) and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>. Let S be a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of q elements and d a positive <a href="/facts/Integer/PUwwrawx">integer</a>. The Hamming graph <i>H</i>(<i>d</i>,<i>q</i>) has <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> set Sd, the set of ordered d-<a href="/facts/Tuple/BI1HIxL8">tuples</a> of elements of S, or sequences of length d from S. Two vertices are <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">adjacent</a> if they differ in precisely one coordinate; that is, if their <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> is one. The Hamming graph <i>H</i>(<i>d</i>,<i>q</i>) is, equivalently, the <a href="/facts/Cartesian_product_of_graphs/wC4JJdyU">Cartesian product</a> of d <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a> Kq. </p><p>In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes. Unlike the Hamming graphs <i>H</i>(<i>d</i>,<i>q</i>), the graphs in this more general class are not necessarily <a href="/facts/Distance-regular_graph/pGAuLWYL">distance-regular</a>, but they continue to be <a href="/facts/Regular_graph/j9dSoLE6">regular</a> and <a href="/facts/Vertex-transitive_graph/042b7rD7">vertex-transitive</a>. </p>