Automorphisms of kaleidoscopical graphs
A regular connected graph Γ of degree s is called kaleidoscopical if there is a (s + 1)-coloring of the set of its vertices such that every unit ball in Γ has no distinct monochrome points. The kaleidoscopical graphs can be considered as a graph counterpart of the Hamming codes. We describe the g...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2007
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/157366 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Automorphisms of kaleidoscopical graphs / I.V. Protasov, K.D. Protasova // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 125–129. — Бібліогр.: 1 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157366 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1573662019-06-21T01:30:26Z Automorphisms of kaleidoscopical graphs Protasov, I.V. Protasova, K.D. A regular connected graph Γ of degree s is called kaleidoscopical if there is a (s + 1)-coloring of the set of its vertices such that every unit ball in Γ has no distinct monochrome points. The kaleidoscopical graphs can be considered as a graph counterpart of the Hamming codes. We describe the groups of automorphisms of kaleidoscopical trees and Hamming graphs. We show also that every finitely generated group can be realized as the group of automorphisms of some kaleidoscopical graphs. 2007 Article Automorphisms of kaleidoscopical graphs / I.V. Protasov, K.D. Protasova // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 125–129. — Бібліогр.: 1 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 05C15, 05C25. http://dspace.nbuv.gov.ua/handle/123456789/157366 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
A regular connected graph Γ of degree s is called
kaleidoscopical if there is a (s + 1)-coloring of the set of its vertices such that every unit ball in Γ has no distinct monochrome
points. The kaleidoscopical graphs can be considered as a graph
counterpart of the Hamming codes. We describe the groups of automorphisms of kaleidoscopical trees and Hamming graphs. We
show also that every finitely generated group can be realized as the
group of automorphisms of some kaleidoscopical graphs. |
| format |
Article |
| author |
Protasov, I.V. Protasova, K.D. |
| spellingShingle |
Protasov, I.V. Protasova, K.D. Automorphisms of kaleidoscopical graphs Algebra and Discrete Mathematics |
| author_facet |
Protasov, I.V. Protasova, K.D. |
| author_sort |
Protasov, I.V. |
| title |
Automorphisms of kaleidoscopical graphs |
| title_short |
Automorphisms of kaleidoscopical graphs |
| title_full |
Automorphisms of kaleidoscopical graphs |
| title_fullStr |
Automorphisms of kaleidoscopical graphs |
| title_full_unstemmed |
Automorphisms of kaleidoscopical graphs |
| title_sort |
automorphisms of kaleidoscopical graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2007 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157366 |
| citation_txt |
Automorphisms of kaleidoscopical graphs / I.V. Protasov, K.D. Protasova // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 125–129. — Бібліогр.: 1 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT protasoviv automorphismsofkaleidoscopicalgraphs AT protasovakd automorphismsofkaleidoscopicalgraphs |
| first_indexed |
2025-07-14T09:48:28Z |
| last_indexed |
2025-07-14T09:48:28Z |
| _version_ |
1837615293608755200 |
| fulltext |
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 2. (2007). pp. 125 – 129
c© Journal “Algebra and Discrete Mathematics”
Automorphisms of kaleidoscopical graphs
I. V. Protasov, K. D. Protasova
Dedicated to V.I. Sushchansky on the occasion of his 60th birthday
Abstract. A regular connected graph Γ of degree s is called
kaleidoscopical if there is a (s + 1)-coloring of the set of its ver-
tices such that every unit ball in Γ has no distinct monochrome
points. The kaleidoscopical graphs can be considered as a graph
counterpart of the Hamming codes. We describe the groups of au-
tomorphisms of kaleidoscopical trees and Hamming graphs. We
show also that every finitely generated group can be realized as the
group of automorphisms of some kaleidoscopical graphs.
1. Introduction
Let Γ(V, E) be a connected graph with the set of vertices V and the set
of edges E. Given any u, v ∈ V and r ∈ N, we denote by d(u, v) the
length of the shortest path between u and v, and put
B(v, r) = {x ∈ V : d(x, v) 6 r}.
Let s > 1 be a natural number. A graph Γ(V, E) is said to be regular
of degree s if |B(v, 1)| = s + 1 for every v ∈ V .
A regular graph Γ(V, E) of degree s is called kaleidoscopical if there
exists a coloring χ : V −→ {0, 1, . . . , s} such that χ is a bijection on every
ball B(v, 1), v ∈ V . For motivation to study kaleidoscopical graphs as a
graph generalization of the Hamming codes see [1, Chapter 6].
Let Γ(V, E) and Γ′(V ′, E′) be kaleidoscopical graphs of degree s and
let χ : V −→ {0, 1, . . . , s}, χ′ : V ′ −→ {0, 1, . . . , s} be its kaleidoscopical
colorings. A mapping f : V −→ V ′ is called a homomorphism if
2000 Mathematics Subject Classification: 05C15, 05C25.
Key words and phrases: kaleidoscopical graph, Hamming pair, kaleidoscopical
tree.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.126 Automorphisms of kaleidoscopical graphs
(i) χ(x) = χ′(f(x)) for every x ∈ V ;
(ii) if {x, y} ∈ E then {f(x), f(y)} ∈ E′.
In the case V = V ′, χ = χ′, a bijective homomorphism f : V −→ V
is called an automorphism. We denote by Aut(Γ(V, E)) the group of all
automorphisms of a kaleidoscopical graph Γ(V, E).
We prove that
• for a kaleidoscopical tree T of degree s, Aut(T ) is a free group of
rank s(s−1)
2 ;
• for a Hamming graph Γ determined by a Hamming pair (X, Y ) in
a group G, Aut(Γ) = Y ;
• for every finitely generated group H, there exists a kaleidoscopical
graph Γ such that Aut(Γ) = H.
2. Kaleidoscopical and Hamming pairs
Let G be a group with the identity e and let X, Y be subsets of G. 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, G = 〈X〉 where 〈X〉 is a subgroup generated by
X;
(ii) e ∈ Y , G = XY ;
(iii) XX
⋂
Y −1Y = XX
⋂
Y Y −1 = {e}.
By this definition, every element g ∈ G has the unique representation
g = xy, x ∈ X, y ∈ Y . We define the standard coloring χ : G −→ X by
the rule χ(g) = x. By [1, Theorem 6.2], Cay(G, X) is a kaleidoscopical
graph. 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 6= y, xy−1 ∈ X}.
A kaleidoscopical pair (X, Y ) is called a Hamming pair if Y is a sub-
group of X. In this case, the kaleidoscopical graph Cay(G, X) is called
a Hamming graph.
Theorem 1. Let (X, Y ) be a kaleidoscopical pair in a group G, χ be the
standard coloring of G. Then the following statement are equivalent
(i) (X, Y ) is a Hamming pair;
(ii) if g1, g2 ∈ G, x ∈ X and χ(g1) = χ(g2) then χ(xg1) = χ(xg2).
Proof. [1, Theorem 6.3].
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.I. V. Protasov, K. D. Protasova 127
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 a finitely generated group is also of
finite index, so Y is finitely generated.
Theorem 2. For every finitely generated group Y , there exist 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.
Proof. Let S be a finite system of generators of Y such that S = S−1,
e ∈ S. For every s ∈ S, we fix some cyclic group 〈as〉 of order 8, and put
G = A × Y, A = ⊕s∈S〈as〉,
X = {a2
ss, a
−2
s s−1 : s ∈ S\{e}} ∪ {A\{a2
s, a
−2
s : s ∈ S \ {e}}}
Then we have
X = X−1, e ∈ X, G = XY, XX ∩ Y = {e},
so (X, Y ) is a Hamming pair in G.
3. Kaleidoscopical semigroups
Let s > 1 be a natural number and X = {0, 1, . . . , s}. The kaleidoscopical
semigroup KS(X) in the alphabet X is a semigroup determined by the
relations xx = x, xyx = x for all x, y ∈ X. For our purposes it is
convenient to identify KS(X) with the set of all non-empty words in X
without the factors xx, xyx where x, y ∈ X. We show that the semigroup
KS(X) acts transitively on the set V of vertices of every kaleidoscopical
graph of degree s with a kaleidoscopical coloring χ : V −→ {0, 1, . . . , s}.
Let x ∈ X and v ∈ V . Pick u ∈ B(v, 1) such that χ(u) = x and put
x(v) = u. Then we extend inductively the action from X onto KS(X)
by the following rule. If w ∈ KS(X), w = xw1, w1 ∈ KS(X) and v ∈ V ,
we put w(v) = x(w1(v)). We observe that the sequence of colors of the
vertices on the shortest path from a vertex v1 ∈ V to a vertex v2 ∈ V
determines a word w ∈ KS(X) such that w(v1) = v2. It follows that the
described action is transitive.
For every x ∈ X, the set KG(X, x) of all words from KS(X) with
the first and the last letter x is a subgroup (with the identity x) of
the semigroup KS(X). To obtain the inverse element to the word w ∈
KG(X, x) it suffices to write w in the reverse order. The group KG(X, x)
is called the kaleidoscopical group in the alphabet X with the identity x.
For proof of the following statements see [1, Chapter 6].
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.128 Automorphisms of kaleidoscopical graphs
• The only idempotents of the semigroup KS(X) are the words x,
xy where x, y ∈ X, x 6= y.
• The kaleidoscopical group KG(X, x) is a free group of rank s(s−1)
2
with the set of free generators
{xyzx : y, z ∈ X\{x}, y < z}.
• The kaleidoscopical semigroup KS(X) is isomorphic to the sand-
wich product L(x) × KG(X, x) × R(x) with the multiplication
(l1, g1, r1)(l2, g2, r2) = (l1, g1r1l2g2, r2),
where L(x) = {yx : y ∈ X}, R(x) = {xy : y ∈ X}.
4. Automorphisms
Lemma. Let Γ(V, E), Γ′(V ′, E′) be kaleidoscopical graphs of degree s >
1 with kaleidoscopical colorings χ : V −→ {0, 1, . . . , s}, χ′ : V ′ −→
{0, 1, . . . , s}. Let f1 : V −→ V ′, f2 : V −→ V ′ be homomorphisms
from Γ(V, E) to Γ′(V ′, E′). If there exists a vertex v ∈ V such that
f1(v) = f2(v) then f1 ≡ f2.
Proof. Since every kaleidoscopical graph is connected, it suffices to show
that f1(u) = f2(u) for every u ∈ B(v, 1). We put w = f1(v) and note
that χ′(w) = χ(v). Since f1, f2 are homomorphisms then f1(u), f2(u) ∈
B(w, 1). Moreover, χ′(f1(u)) = χ(u), χ′(f2(u)) = χ(u) but B(w, 1) has
only one point of color χ(u) so f1(u) = f2(u).
A regular tree T of degree s with fixed kaleidoscopical s-coloring of
the set of its vertices is called a kaleidoscopical tree of degree s.
By [1, Theorem 6.4], every kaleidoscopical graph of degree s is a
homomorphic image of T .
Theorem 3. Let T be a kaleidoscopical tree of degree s > 1. Then
Aut(T ) is a free group of rank s(s−1)
2 .
Proof. In view of Section 3, it suffices to show that Aut(T ) is isomorphic
to the kaleidoscopical group KG(X, x) where X = {0, 1, . . . , s}, x ∈ X.
We fix an arbitrary vertex v of T of color x. Given an arbitrary f ∈
Aut(T ), we choose wf ∈ KG(X, x) such that wf (v) = f(v). Thus, we
have defined the mapping
ϕ : Aut(T ) −→ KG(X, x), ϕ(f) = wf .
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.I. V. Protasov, K. D. Protasova 129
By Lemma, ϕ is injective. Since Aut(T ) acts transitively on the set
of vertices of color x, then ϕ is surjective. Hence, f is a bijection. Given
any f, g ∈ Aut(T ), we have
ϕ(f, g) = wfg = wfwg = ϕ(f)ϕ(g),
so ϕ is an isomorphism.
Theorem 4. Let G be a group with a Hamming pair (X, Y ), Γ =
Cay(G, X). Then Aut(Γ) is isomorphic to Y.
Proof. Let χ : G −→ {0, 1, . . . , s} be the standard coloring (see Section
2) of Γ. Clearly, χ is stable on every left coset of G by Y . Hence, every
element y ∈ Y determines an automorphism of Γ by the rule fy(g) =
gy−1. On the other hand, let h be an arbitrary automorphism of Γ.
Then h(e) = y−1 for some y ∈ Y . By Lemma, h = fy.
Theorem 5. Every finitely generated group H is isomorphic to the group
Aut(Γ) for some kaleidoscopical graph Γ.
Theorem 6. By Theorem 2, there exists a group G with a Hamming
pair (X, Y ) such that Y is isomorphic H. Then we apply Theorem 4.
References
[1] I.Protasov, T.Banakh,Ball Structures and Colorings of Groups and Graphs , Math.
Stud. Monogr. Ser. V.11, 2003.
Contact information
I. V. Protasov, K.
D. Protasova
Department of Cybernetics, Kyiv National
University, Volodimirska 64, Kyiv 01033,
UKRAINE
E-Mail: protasov@unicyb.kiev.ua,
islab@unicyb.kiev.ua
|