Kaleidoscopical and Hamming graphs
by
Ksenia Protasova
Department of Cybernetics, Kyiv National University

Let G(V, E) be a connected graph with the set of vertices V and the set of edges E. Given u, v ∈ V and r ∈ N, we denote by d(u, v) the length of a shortest path between u and v, and put B(v, r)={ x ∈ V: d(x, v) ≤ r}. Let s > 1 be a natural number. A graph G(V, E) is said to be regular of degree s if | B(v, 1) | = s+1 for every v ∈ V.

A regular graph G(V, E) of degree s is called kaleidoscopical if there exists a coloring c: V→{0, 1, …, s } such that c is a bijection on every ball B(v, 1), v ∈ V.

Let G be a group with the identity e and let X, Y be subsets of G. Next definition is a correction of corresponding definition from [1, p.60].

Definition. We say that (X, Y) is a kaleidoscopical pair in G provided that X is finite and the following conditions hold

(i) e ∈ X, X=X ^-1 and G= < X > , where < X > is a subgroup generated by X;

(ii) e ∈ Y, G=XY;

(iii) XX∩Y^-1 Y = XX∩YY^-1={ e }.

By this definition, every element g ∈ G has the unique representation g=xy, x ∈ X, y ∈ Y. We define the standard coloring c: G→ X by the rule c(g)=x. We remind that the Cayley graph Cay(G, X) is a graph with the set of vertices G and the set of edges {{x, y}: x, y ∈ G, x ≠ y, xy^-1 ∈ X}.

Theorem 1 Let G be a group with kaleidoscopical pair (X, Y). Then Cay(G, X) with standard coloring c is a kaleidoscopical graph.

A kaleidoscopical pair (X, Y) is called a Hamming pair if Y is a subgroup of X. In this case, the kaleidoscopical graph Cay(G, X) is called a Hamming graph.

Theorem 2 Let (X, Y) be a kaleidoscopical pair in a group G, c be the standard coloring of G. Then the following statements are equivalent

(i) (X, Y) is a Hamming pair;

(ii) if g₁ g₂ ∈ G, x ∈ X and c(g₁)=c(g₂) then c(x, g₁)=c(x g₂).

Let (X, Y) be a Hamming pair in a group G. Since X is finite, G is finitely generated. Since G=XY then Y is a subgroup of finite index. Every subgroup of finite index of finitely generated group is also finitely generated, so Y is finitely generated.

Theorem 3 For every finitely generated group Y, there exists a group G and a finite subset X ⊆ G such that Y is a subgroup of G and (X, Y) is a Hamming pair in G.

References

1. I.Protasov, T.Banakh, Ball Structures and Colorings of Groups and Graphs, Monogr. Ser. V.11, VNTL, Lviv, 2003, 147 p.

Date received: March 14, 2008