Rainbow graphs and semigroups
We give an algebraic characterization of rainbow graphs. A connected graph Γ is called rainbow if there is a vertex coloring of Γ, which is bijective on the set of neighbors of each vertex of Γ.
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84296 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Rainbow graphs and semigroups / K.D. Protasova, Т.М. Provotar // Доп. НАН України. — 2012. — № 7. — С. 43-47. — Бібліогр.: 6 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84296 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-842962015-07-07T03:01:56Z Rainbow graphs and semigroups Protasova, K.D. Provotar, Т.М. Інформатика та кібернетика We give an algebraic characterization of rainbow graphs. A connected graph Γ is called rainbow if there is a vertex coloring of Γ, which is bijective on the set of neighbors of each vertex of Γ. Отримано алгебраїчну характеризацiю веселкових графiв. Зв’язний граф Γ називається веселковим, якщо iснує розфарбування множини вершин Γ, що є бiєктивним на множинi сусiдiв кожної вершини Γ. Получена алгебраическая характеризация радужных графов. Связный граф Γ называется радужным, если существует раскраска множества вершин Γ, биективная на множестве соседей для каждой вершины Γ. 2012 Article Rainbow graphs and semigroups / K.D. Protasova, Т.М. Provotar // Доп. НАН України. — 2012. — № 7. — С. 43-47. — Бібліогр.: 6 назв. — англ. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/84296 519.1 en Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Protasova, K.D. Provotar, Т.М. Rainbow graphs and semigroups Доповіді НАН України |
| description |
We give an algebraic characterization of rainbow graphs. A connected graph Γ is called rainbow
if there is a vertex coloring of Γ, which is bijective on the set of neighbors of each vertex of Γ. |
| format |
Article |
| author |
Protasova, K.D. Provotar, Т.М. |
| author_facet |
Protasova, K.D. Provotar, Т.М. |
| author_sort |
Protasova, K.D. |
| title |
Rainbow graphs and semigroups |
| title_short |
Rainbow graphs and semigroups |
| title_full |
Rainbow graphs and semigroups |
| title_fullStr |
Rainbow graphs and semigroups |
| title_full_unstemmed |
Rainbow graphs and semigroups |
| title_sort |
rainbow graphs and semigroups |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2012 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84296 |
| citation_txt |
Rainbow graphs and semigroups / K.D. Protasova, Т.М. Provotar // Доп. НАН України. — 2012. — № 7. — С. 43-47. — Бібліогр.: 6 назв. — англ. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT protasovakd rainbowgraphsandsemigroups AT provotartm rainbowgraphsandsemigroups |
| first_indexed |
2025-07-06T11:17:11Z |
| last_indexed |
2025-07-06T11:17:11Z |
| _version_ |
1836896106071457792 |
| fulltext |
УДК 519.1
© 2012
K.D. Protasova, Т.М. Provotar
Rainbow graphs and semigroups
(Presented by Corresponding Member of the NAS of Ukraine S. I. Lyashko)
We give an algebraic characterization of rainbow graphs. A connected graph Γ is called rainbow
if there is a vertex coloring of Γ, which is bijective on the set of neighbors of each vertex of Γ.
A rainbow graph [3] is a connected graph Γ with the set of vertices V (Γ) and the set of edges
E(Γ) that can be vertex-colored χ : V (Γ) −→ κ so that every color x ∈ κ is represented once,
and only once, among the neighbors N(v) = {u ∈ V (Γ): {u, v} ∈ E(Γ)} of each vertex v ∈ V (Γ).
For applications of rainbow graphs, see [1]. If one removes the edge-matching of the monochrome
edges of a rainbow graph, one gets a kaleidoscopical graph [2, Chapter 6].
Let κ be a cardinal. A rainbow semigroup RS(κ) is a semigroup in the alphabet κ determined
by the relations xxx = x, xyx = x for all x, y ∈ κ. We identify RS(κ) with the set of all non-
empty words in κ with no factors xxx, xyx.
For x ∈ κ, a rainbow group RG(κ, x) is a subset of RS(κ) containing x and all words of the
form xwx, w ∈ RS(κ). The word xx is the identity of RG(κ, x), x−1 = x, and (xwx)−1 = xxw̃xx,
where w̃ is the word w written in the reverse order.
Theorem 1. For any cardinal κ and each x ∈ κ, the following statements hold:
(i) the idempotents of RS(κ) are only yz, where y, z ∈ κ;
(ii) RG(κ, x) is a free product of the cyclic group 〈x〉 of order 2 and the family of infinite
cyclic groups {〈xabx〉 : a, b ∈ κ, a 6= x, b 6= x};
(iii) RS(κ) is a sandwich product RS(κ) = L(x)×RG(κ, x)×R(x), where L(x) = {yx : y ∈
∈ κ}, R(x) = {xy : y ∈ κ}, and the multiplication (l1, w1, r1)(l2, w2, r2) = (l1, w1r1l2w2, r2).
Let κ be a cardinal, x ∈ κ. An equivalence ∼ on RS(κ) is called a rainbow equivalence if,
for any w1, w2 ∈ RS(κ), we have
• w1 ∼ w2 =⇒ l(w1) = l(w2), where l(w) is the first letter of w;
• w1 ∼ w2 =⇒ yw1 = yw2 for each y ∈ κ;
• l(w) = y =⇒ w and yw are not equivalent;
• w ∼ wxx for each w ∈ KS(κ).
Each rainbow equivalence ∼ on RS(κ) determines the rainbow graph Γ(κ, k) as follows. The
set V (Γ) of vertices of Γ is a factor-set RS(κ)/ ∼= {[w] : w ∈ RS(κ)}, where [w] is the class of
equivalence ∼ containing w. By definition, {u, v} ∈ E(Γ) if and only if u 6= v, and there exists
w ∈ u such that yw ∈ v. Then the mapping χ : V (Γ) −→ κ defined by χ([w]) = l(w) does not
depend on the choice of w and determines a rainbow coloring of Γ.
In turn, every rainbow equivalence ∼ on RS(κ) is uniquely determined by the subgroup
Sx = [xx]
⋂
RG(κ, x)
of RG(κ, x) because
w1 ∼ w2 ⇐⇒ l(w1) = l(w2) ∧ xw1xx ∼ xw2xx ⇐⇒ (xw1xx)
−1(xw2xx) ∈ Sx.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 43
We say that two rainbow graphs Γ1, Γ2 with rainbow colorings χ1 : V (Γ1) −→ κ,
χ2 : V (Γ2) −→ κ are rainbow isomorphic if there exists a bijection f : V (Γ1) −→ V (Γ2) such that
• ∀u, v ∈ V (Γ1) : {u, v} ∈ E(Γ1) ⇐⇒ {f(u), f(v)} ∈ E(Γ2);
• ∀u ∈ V (Γ1) : χ1(u) = χ2(f(u)).
Now, we are ready to characterize all rainbow graphs up to rainbow isomorphisms.
Let Γ be a rainbow graph with rainbow coloring χ : V (Γ) −→ κ. We define a transitive action
of RS(κ) on the set V (Γ) as follows. Let v ∈ V (Γ), x ∈ κ. Pick u ∈ N(v) such that χ(u) = x
and put x(v) = u. Then we extend the action onto KS(κ) inductively. If w = RS(κ), w = xw′,
x ∈ κ, we put w(v) = χ(w′(v)). Given any v1, v2 ∈ V (Γ), the sequence of colors of the vertices
on a path from v1 to v2 determines a word w ∈ RS(κ) such that w(v1) = v2, so RS(κ) acts on
V (Γ) transitively. Clearly, the group RG(κ, x) acts transitively on the set of vertices of color x.
We fix v ∈ V (Γ) with χ(v) = x, determine a rainbow equivalence ∼ on RS(κ) by the rule
w ∼ w′ ⇐⇒ w(v) = w′(v),
and note that the graphs Γ and Γ(κ,∼) are rainbow isomorphic via the bijection f : V (Γ) −→
→ KS(κ)/ ∼, f(u) = {w ∈ KS(κ) : w(v) = u}.
Thus, we get the following statement.
Theorem 2. For every rainbow graph Γ with rainbow coloring χ : V (Γ) −→ κ, there exists
a rainbow equivalence ∼ on RS(κ) such that Γ and Γ(κ,∼) are rainbow isomorphic. Every rainbow
equivalence on RS(κ) is uniquely determined by some subgroup of RG(κ, x).
Let Γ(V,E) be a connected graph with the set of vertices V , and let the set of edges E, d be
the path metric on V , B(v, r) = {u ∈ V : d(v, u) 6 r}, v ∈ V , r ∈ ω = {0, 1, . . .}.
A graph Γ(V,E) is called kaleidoscopical [6] if there exists a coloring (a surjective mapping)
χ : V −→ κ, κ is a cardinal such that the restriction χ | B(v, 1): B(v, 1) −→ κ is a bijection on
each unit ball B(v, 1), v ∈ V . For kaleidoscopical graphs, see also [2, Chapter 6] and [5].
Let G be a group, and let X be a transitive G-space with the action G×X −→ X, (g, x) 7−→
→ gx. A subset A of X, |A| = κ is said to be a kaleidoscopical configuration [4] if there exists
a coloring χ : X −→ κ such that, for each g ∈ G, the restriction χ | gA : gA −→ κ is a bijection.
We note that kaleidoscopical graphs and kaleidoscopical configurations can be considered as
partial cases of kaleidoscopical hypergraphs defined in [2, p.5]. Recall that a hypergraph is a pair
(X,F), where X is a set, F is a family of subsets of X.
A hypergraph (X,F) is said to be kaleidoscopical if there exists a coloring χ : X −→ κ such
that, for each F ∈ F, the restriction χ | F : F −→ κ is a bijection.
Clearly, a graph Γ(V,E) is kaleidoscopical if and only if the hypergraph (V, {B(v, 1): v ∈ V })
is kaleidoscopical. A subset A of a G-space X is kaleidoscopical if and only if the hypergraph
(X, {g(A) : g ∈ G}) is kaleidoscopical.
We say that two hypergraphs (X1,F1), (X2,F2) with kaleidoscopical colorings χ1 : X1 −→ κ,
χ2 : X2 −→ κ are kaleidoscopically isomorphic if there is a bijection f : X1 −→ X2 such that
• ∀A ⊆ X1 : A ∈ F1 ⇐⇒ f(A) ∈ F2;
• ∀x ∈ X1 : χ1(x) = χ2(f(x)).
We describe an algebraic construction which gives all kaleidoscopical graphs up to isomor-
phisms.
The kaleidoscopical semigroup KS(κ) is a semigroup in the alphabet κ determined by the
relations xx = x, xyx = x for all x, y ∈ κ. For our purposes, it is convenient to identify KS(κ)
with the set of all non-empty words in κ with no factors xx, xyx, where x, y ∈ κ.
44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №7
For every x ∈ κ, the set KG(κ, x) of all words from KS(κ) with the first and the last letter x
is a subgroup (with the identity x) of the semigroup KS(κ). To obtain the inverse element to
the word w ∈ KG(κ, x), it suffices to write w in the inverse order. The group KG(κ, x) is called
the kaleidoscopical group in the alphabet κ with the identity x.
For finite cardinals κ, the following theorem is proved in [2, pp. 64–66]: but corresponding
arguments work for arbitrary κ.
Theorem 3. For any cardinal κ, the following statements hold:
(i) idempotents of the semigroup KS(κ) are the only words x, xy, where x, y ∈ κ, x 6= y,
(ii) the kaleidoscopical group KG(k, x) is a free group with the set of free generators
{xyzx : y, z ∈ κ \ {x}, y 6= z},
(iii) the kaleidoscopical semigroup KS(κ) is isomorphic to the sandwich product L(x) ×
× KG(κ, x) × R(x) with the multiplication
(l1, g1, r1)(l2, g2, r2) = (l1, g1r1l2g2, r2),
where L(x) = {yx : y ∈ κ}, R(x) = {xy : y ∈ κ}.
We fix x ∈ κ, denote the first letter of the word w ∈ KS(κ) by æ(w), and say that an
equivalence ∼ on KS(κ) is kaleidoscopical if, for all w,w′ ∈ KS(κ) and y ∈ κ,
w ∼ w′ =⇒ æ(w) = æ(w′) ∧ yw = yw′,
w ∼ w′ ⇐⇒ wx ∼ w′x.
Let [w] be the class of equivalence ∼ containing w ∈ KS(κ).
We put
Sx = [x]
⋂
KG(κ, x),
observe that Sx is a subgroup of KG(κ, x), and show that ∼ is uniquely determined by Sx:
w ∼ w′ ⇐⇒ æ(w) = æ(w′) ∧ xwx ∼ xw′x ⇐⇒ (xwx)−1(xw′x) ∈ Sx.
We see also that any subgroup of KG(κ, x) can be taken as Sx to determine a kaleidoscopical
equivalence on KS(κ).
A kaleidoscopical equivalence ∼ determines a graph Γ(κ,∼) with the set of vertices KS(κ)/ ∼
and the set of edges E defined by the rule:
(u, v) ∈ E ⇐⇒ ∃w ∈ u∃ y ∈ κ : æ(w) 6= y ∧ yw ∈ v.
A coloring χ : KS(κ)/ ∼−→ κ defined by χ([w]) = æ(w) shows that Γ(κ,∼) is kaleidoscopical.
Now let Γ(V,E) be a kaleidoscopical graph with kaleidoscopical coloring χ : V −→ κ. We
define a transitive action of the semigroup KS(κ) on the set V as follows. Let v ∈ V , x ∈ κ.
Pick u ∈ B(v, 1) such that χ(u) = x and put x(v) = u. Then we extend the action onto KS(κ)
inductively. If w = KS(κ), w = xw′, w′ ∈ KS(κ), x ∈ κ, we put w(v) = x(w′(v)). Given any
v1, v2 ∈ V , the sequence of colors of the vertices on a path from v1 to v2 determines a word
w ∈ KS(κ) such that w(v1) = v2, so KS(κ) acts on V transitively. Clearly, the group KG(κ, x)
acts transitively on the set χ−1(x) of vertices of color x.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 45
We fix v ∈ V with χ(v) = x, determine a kaleidoscopical equivalence ∼ on KS(κ) by the rule
w ∼ w′ ⇐⇒ w(v) = w′(v),
and note that the graphs Γ(V,E) and Γ(κ,∼) are kaleidoscopically isomorphic via the bijection
f : V −→ KS(κ)/ ∼, f(u) = {w ∈ KS(κ) : w(v) = u}.
All above considerations are focused in the following theorem.
Theorem 4. For every kaleidoscopical graph Γ(V,E) with kaleidoscopical coloring χ : V −→
→ κ, there exists a kaleidoscopical equivalence ∼ on the semigroup KS(κ) such that Γ(V,E) is
kaleidoscopically isomorphic to Γ(κ,∼). Every kaleidoscopical equivalence ∼ on KS(κ) is uni-
quely determined by some subgroup of the group KG(κ, x).
Every group G can be considered as a G-space with the left regular action (g, x) 7−→ yx.
Let A be a kaleidoscopical configuration in G. By [4, Corollary 1.3], A is complemented, i. e.
there exists a subset B of G such that the multiplication A×B −→ G, (a, b) 7−→ ab is bijective.
Let A be a system of generators of a group G such that A = A−1 and e ∈ A, e is the identity
of G. We consider the Cayley graph Cay(G,A) with the set of vertices G and the set of edges E
defined by the rule:
(g, h) ∈ E ⇐⇒ g−1h ∈ A, g 6= h.
Clearly, Cay(G,A) is connected. Assume that Cay(G,A) is kaleidoscopical with kaleidoscopi-
cal coloring χ : G −→ |A|. Since B(g, 1) = gA and χ is bijective on each ball B(g, 1), we see
that A is a kaleidoscopical configuration. On the other hand, if A is a kaleidoscopical confi-
guration in G with kaleidoscopical coloring χ : G −→ A, then χ is bijective on each set gA. So,
Cay(G,A) is kaleidoscopical. Thus, we get the following theorem.
Theorem 5. Let G be a group, and let A be a system of generators of G such that A = A−1
and e ∈ A. Then A is a kaleidoscopical configuration if and only if Cay(G,A) is kaleidoscopical.
We conclude the paper with two open questions.
Question 1. How can one detect whether a kaleidoscopical hypergraph is kaleidoscopically
isomorphic to a hypergraph of unit balls of some kaleidoscopical graph?
Question 2. How can one detect whether a kaleidoscopical hypergraph is kaleidoscopically
isomorphic to a hypergraph determined by a kaleidoscopical configuration in a G-space?
1. Lazebnik F., Woldar A. J. General properties of some families of graphs defined by systems of equations //
J. Graph Theory. – 2001. – 38. – P. 65–86.
2. Protasov I., Banakh T. Ball structures and colorings of groups and graphs. – Lviv: VNTL, 2003. – 148 p.
3. Woldar A. J. Rainbow graphs // Codes and Designs, edited by K.T. Arasu and A. Seress. – Berlin: W. de
Gruyter, 2002. – P. 313–322.
4. Banakh T., Petrenko O., Protasov I., Slobodianuk S. Kaleidoscopical configurations in G-space // Electron.
J. Combinatorics. – 2012. – 19. – 16 p.
5. Protasov I.V., Protasova K.D. Kaleidoscopical graphs and Hamming codes // Voronoi’s Impact on Modern
Science. – Kiev: Institute Math. of the NAS of Ukraine, 2008. – P. 240–245.
6. Protasova K.D. Kaleidoscopical graphs // Mat. Studii. – 2002. – 18. – P. 3–9.
Received 23.12.2011Taras Schevchenko Kyiv National University
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №7
K.Д. Протасова, T.M. Провотар
Веселковi графи i напiвгрупи
Отримано алгебраїчну характеризацiю веселкових графiв. Зв’язний граф Γ називається ве-
селковим, якщо iснує розфарбування множини вершин Γ, що є бiєктивним на множинi
сусiдiв кожної вершини Γ.
K.Д. Протасова, T.M. Провотар
Радужные графы и полугруппы
Получена алгебраическая характеризация радужных графов. Связный граф Γ называется
радужным, если существует раскраска множества вершин Γ, биективная на множестве
соседей для каждой вершины Γ.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 47
|