Hamming graph

Hamming graph --- граф Хэмминга.

Given a graph [math]\displaystyle{ = (V,E) }[/math], [math]\displaystyle{ G }[/math] is mathcalled Hamming graph if each vertex [math]\displaystyle{ x \in V }[/math] can be labeled by a word [math]\displaystyle{ a(x) }[/math] (of fixed length) over some symbol set [math]\displaystyle{ \Sigma }[/math] such that

[math]\displaystyle{ H(a(x),a(y)) = d_{G}(x,y) }[/math]

for arbitrary [math]\displaystyle{ x, y \in V }[/math]. Here [math]\displaystyle{ a(x) }[/math] is termed the address of [math]\displaystyle{ x }[/math], and [math]\displaystyle{ H(a,b) }[/math] stands for the Hamming distance of the addresses [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math], that is, the number of positions [math]\displaystyle{ k }[/math] such that the [math]\displaystyle{ k }[/math]-th symbol in [math]\displaystyle{ a }[/math] differs from the [math]\displaystyle{ k }[/math]-th symbol in [math]\displaystyle{ b }[/math]. Futher, [math]\displaystyle{ d_{G}(x,y) }[/math] denotes the length of a shortest chain in [math]\displaystyle{ G }[/math] between [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math]. [math]\displaystyle{ G }[/math] is called a binary Hamming graph if [math]\displaystyle{ \Sigma = \{0,1\} }[/math].