ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P2.06 / 259–269
https://doi.org/10.26493/1855-3974.1926.6ad
(Also available at http://amc-journal.eu)
Decompositions of the automorphism groups
of edge-colored graphs into the direct product of
permutation groups
Mariusz Grech *
Wrocław University of Science and Technology,
Wybrzeże Wyspiańskiego Str. 27, Wrocław, Poland
Received 31 January 2019, accepted 1 June 2021, published online 11 October 2021
Abstract
In the paper Graphical complexity of products of permutation groups, M. Grech, A. Jeż,
and A. Kisielewicz have proved that the direct product of automorphism groups of edge-
colored graphs is itself the automorphism groups of an edge-colored graph. In this paper,
we study the direct product of two permutation groups such that at least one of them fails
to be the automorphism group of an edge-colored graph. We find necessary and sufficient
conditions for the direct product to be the automorphism group of an edge-colored graph.
The same problem is settled for the edge-colored digraphs.
Keywords: Colored graph, automorphism group, permutation group, direct product.
Math. Subj. Class. (2020): 05E18
1 Introduction
For permutation groups (A, V ), (B,W ), the direct product of A and B (with product ac-
tion) is a permutation group (A×B, V ×W ) with the action given by
(a, b)(x, y) = (a(x), b(y)).
The study of the direct product of automorphism groups of graphs was initiated by
G. Sabidussi [19] in 1960. The problem was taken up in 1971 by M. Watkins [20]. In
1972, L. Nowitz and M. Watkins [21], and independently W. Imrich [13], have described
the conditions under which the direct product of regular permutation groups that are auto-
morphism groups of graphs is itself the automorphism group of a graph. This result was
*Supported in part by Polish NCN grant UMO-2016/21/B/ST1/03079.
E-mail address: mariusz.grech@pwr.edu.pl (Mariusz Grech)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
260 Ars Math. Contemp. 21 (2021) #P2.06 / 259–269
a contribution to the description of all regular automorphism groups of graphs, which has
been completed in 1978 by C. Godsil [5] for graphs, and in 1980 by L. Babai [1] for di-
graphs. The above results in [13, 21] have been extended to arbitrary permutation groups
in [6], where the description of the conditions, under which the direct product of automor-
phism groups of graphs is itself an automorphism group of a graph, is given. In [8], the
same is done for digraphs.
All the above results are motivated more or less directly by trying to make a contribution
to the solution of the concrete version of König problem asking about a characterization
of those permutation groups that are the automorphism groups of graphs (see [14]). There
are a number of results (see e.g. [9, 10, 18] and [14]) showing that it is more natural and
effective to study the automorphism groups of (edge-)colored graphs (rather than simple
graphs), which is essentially the approach suggested by Wielandt [23].
In [14], A. Kisielewicz has introduced the notion of graphical complexity of permuta-
tion groups and suggested the study of constructions of permutation groups in this context.
By G(k), we denote the class of the automorphism groups of k-edge-colored graphs (those
using at most k colors), and by GR, the union of all the classes G(k), which in Wielandt’s
terminology [23] is the class of 2∗-closed groups. Similarly, by DG(k) we denote the class
of the automorphism groups of k-edge-colored digraphs, and by DGR the union of all the
classes DG(k) (which in Wielandt’s terminology is the class of 2-closed groups). Clearly,
GR ⊆ DGR, and G(k) ⊆ DG(k), for any k.
The main general problem is to determine which permutation groups are the automor-
phism groups of edge-colored graphs. Various aspects of this general problem are investi-
gated. For example, it leads to the concept of colored totally symmetric graphs, that was
described in [11, 12]. This coincides to a large extent with the research on homogeneous
factorization of graphs (c.f., [4, 15, 16]). One direction of research is to consider various
constructions of permutation groups and to ask the following question: is it true that if the
components of the construction belong to a particular class G(k), then the result belongs
to G(k), as well? And if not, how many colors one must add to make sure that the result of
the construction belong to G(k + r)?
For the direct product the problem has been solved in [9, Theorem 2.2].
Theorem 1.1 (Grech, Jeż, Kisielewicz). If permutation groups A,B ∈ GR, then A×B ∈
GR. Also, if A,B ∈ DGR, then A×B ∈ DGR.
Note that the second part of this theorem was also shown in [3, Theorem 5.1]
This result, with some exceptions, is also true for particular classes G(k) and DG(k)
(for details see [7]). In this paper we consider the converse of the theorem above. We
show that while for DGR the converse also holds (Theorem 3.1), for GR it is not generally
true. The main results is Theorem 3.2 characterizing the conditions under which the direct
product of two arbitrary permutation groups belongs to GR.
2 Preliminaries
We assume that the reader has basic knowledge in the areas of graphs and permutation
groups, so we omit an introduction to standard terminology. If necessary, additional details
can be found in [2, 24].
By a k-edge-colored graph G, we mean a pair G = (V,E), where V is the set of
vertices of G, and E the edge-color function from the set P2(V ) of unordered pairs of
M. Grech: Decompositions of the automorphism groups of edge-colored graphs into the . . . 261
vertices into the set of colors {0, . . . , k − 1} (E : P2(V ) → {0, . . . , k − 1}). Thus, G is a
complete simple graph with colored edges. Similarly, by a k-edge-colored digraph G, we
mean a pair (V,E) where E is a color function from the set of ordered pairs of different
elements of V to the set of colors {0, . . . , k − 1} (E : ((V × V ) \ {(v, v); v ∈ V }) →
{0, . . . , k − 1}).
An automorphism of an edge-colored graph G is a permutation a of the set V preserv-
ing the edge function: E({v, w}) = E({a(v), a(w)}), for all v, w ∈ V . The group of
automorphisms of G will be denoted by Aut(G), and considered as a permutation group
(Aut(G), V ) acting on the set of the vertices V . Edge-colored digraphs are defined simi-
larly.
All groups considered in this paper are groups of permutations. They are considered up
to permutation group isomorphism. Generally, a permutation group A acting on a set V is
denoted (A, V ) or just A, if the set V is clear from the context or not important. By Sn we
denote the symmetric group on n elements, and by In, the one element group acting on n
elements (consisting of the identity only, denoted by id).
We shall consider the natural actions of a given permutation group A = (A, V ) on the
sets of ordered and unordered pairs of V , V × V and P2(V ), respectively. Let a ∈ A and
v, w ∈ V . Then, the first action of a is given by the formula
a((v, w)) = (a(v), a(w)),
while the second action is given by
a({v, w}) = {a(v), a(w)}.
The orbits of A in the action on V × V are called orbitals of A. Since in this paper we
concider graphs (digraphs) without loops, we exclude trivial orbitals consisting of pairs of
the form (v, v). For two orbitals O1, O2 we say that O1 is paired with O2 if and only if
O2 = {(w, v) : (v, w) ∈ O1}. We call an orbital O self-paired if it is paired with itself.
Moreover, we say that a permutation a transposes O1 and O2, if a(O1) = O2.
In addition, the orbits of A in the action on P2(V ) will be called here 2∗-orbitals. Note
that we can think of a 2∗-orbital either as a self paired orbital or as a pair of paired orbitals.
Since A×I1 = I1×A = A (up to permutation isomorphism), in this paper, we consider
only the direct products A×B with both the permutation groups A,B different from I1.
Let A = (A, V ) be a permutation group, and let O∗1 , . . . O
∗
k be all the 2
∗-orbitals of A.
We define an edge-colored graph G∗(A) (called 2∗-orbital graph) as follows.
G∗(A) = (V,E), where E : P2(V ) → {0, . . . k − 1}.
E({v, w}) = i if and only if the edge {v, w} belongs to the 2∗-orbital O∗i .
Now, we define A∗ = Aut(G∗(A)). Obviously, A ⊆ A∗. It should be clear that A∗ is
the smallest permutation group on V that contains A and belongs to GR. (Indeed, if G′
is a colored graph whose automorphism group contains A, then edges in each 2∗-orbital
of A have to have the same color. Hence, each permutation in Aut(G∗(A)) belongs to
Aut(G′).) In particular, we have that A ∈ GR if and only if A = A∗.
Similarly we define the orbital digraph G(A) replacing 2∗-orbitals by orbitals. In the
same way, denoting A = Aut(G(A)), we have that A is the smallest permutation group on
X that contains A and belongs to DGR. Moreover, A ∈ DGR if and only if A = A. In
addition, A ⊆ A ⊆ A∗.
For direct products of permutation groups we have the following inclusions
262 Ars Math. Contemp. 21 (2021) #P2.06 / 259–269
Lemma 2.1.
(i) A×B ⊆ Aut(G∗(A×B)) ⊆ A∗ ×B∗,
(ii) A×B ⊆ Aut(G(A×B)) ⊆ A×B,
Proof. The first inclusion holds for all permutation groups, as it was remarked above. We
prove the second inclusion.
Consider the edges of the form {(v1, w), (v2, w)}, which we may refer as edges be-
longing to the rows. Obviously, they form a union of 2∗-orbitals, and therefore the edges
{(v1, w1), (v2, w2)} with w1 ̸= w2 in Aut(G∗(A × B)) have different colors than those
belonging to the rows. The same is true for columns, i.e. the edges of the form {(w, v1),
(w, v2)}. Thus, rows can be mapped only onto rows by automorphisms of G∗(A × B),
and columns can be mapped only onto columns. This implies that Aut(G∗(A × B)) ⊆
A1 × B1, for some A1 and B1. Now let (a, b) ∈ Aut(G∗(A × B)). Then, the edges
(a, b)({(v1, w), (v2, w)}) and {(v1, w), (v2, w)} have the same color. Therefore, there is
(a1, b1) ∈ A × B such that (a1, b1)({(v1, w), (v2, w)}) = {(v1, w), (v2, w)}. Hence,
(a−11 a, b
−1
1 b) ∈ Aut(G∗(A × B)) preserves the row with the edge {(v1, w), (v2, w)}.
Since every row in Aut(G∗(A × B)) is a copy of G∗(A) (up to recoloring), we have that
a−11 a ∈ A∗, which implies that a ∈ A∗. In a similar way, b ∈ B∗, which completes the
proof of the first part of the theorem. The second part is proved similarly.
We observe that if C = Aut(G∗(A × B)), then C∗ may be a proper subgroup of
A∗ × B∗. The smallest example is I2 × I2, where Aut(G∗(I2 × I2)) = I2 × I2, while
I2
∗ × I2∗ = S2 × S2.
We observe also that if a ∈ A∗, then it not only preserves 2∗-orbitals of A (by defini-
tion), but it also preserves orbits of A.
Lemma 2.2. Let A ̸= I2 be a permutation group. If a ∈ A∗, then a preserves the orbits of
A.
Proof. Let Qt, t ∈ {1, . . . ,m} be the orbits of A. The claim is obvious if A = It for any
t > 2, so we may assume that there is an orbit Qi that has at least two elements. Then, the
set P2(Qi) is nonempty. Moreover, it is clear that P2(Qi) is the union of 2∗-orbitals of A.
Hence, the edges of G∗(A) that belong to P2(Qi) have different colors than the remaining
edges. This implies that a preserves the orbit Qi.
Now, if there is another orbit Qt, t ̸= i, then obviously, the edges {v, w} with v ∈ Qi
and w ∈ Qt have different colors than the remaining edges. Consequently, every orbit is
preserved by a.
3 Results
We proceed to the main problem of this paper to describe conditions under which A × B
belongs to GR or DGR. The case of directed graphs is pretty easy.
Theorem 3.1. Let A and B be permutation groups. Then, A × B ∈ DGR if and only if
both A and B are in DGR.
Proof. In view of the Theorem 1.1 quoted in the introduction we need to prove merely the
“only if” part. It is enough to prove, without loss of generality, that if A /∈ DGR, then
M. Grech: Decompositions of the automorphism groups of edge-colored graphs into the . . . 263
A × B /∈ DGR. Let A = (A, V ) and B = (B,W ). We assume that A /∈ DGR. Then,
A ̸= I2 (since I2 ∈ DGR). Moreover, we may choose a ∈ A \ A. By definition, it
preserves all orbitals of A.
Let idB be the identity in the permutation group B. We show that the permutation
(a, idB) belongs to Aut(G(A × B)). To this end, we show that for every directed edge
e = ((v1, w1), (v2, w2)), where v1, v2 ∈ V , w1, w2 ∈ W , the image (a, idB)(e) has the
same color as e.
Assume first that v1 ̸= v2. Since a preserves orbitals of A, for every pair (v1, v2),
there is a permutation a2 ∈ A such that a(v1) = a2(v1) and a(v2) = a2(v2). We have
(a, idB)(e) = (a2, idB)(e), and therefore the directed edges (a, idB)(e) and e belong to
the same orbital of A × B. So, by the definition of the edge-colored digraph G(A × B),
(a, idB)(e) and e have the same color in G(A×B).
If v1 = v2, then since A ̸= I2, we may use Lemma 2.2 and find a permutation a1 ∈ A
such that a1(v1) = a(v1). We have (a, idB)(e) = (a1, idB)(e), and therefore the directed
edges (a, idB)(e) and e belong to the same orbital of A×B. So, they have the same color.
Thus, in all the cases (a, idB) ∈ Aut(G(A × B)), but (a, idB) does not belong to
A×B. Therefore, A×B /∈ DGR.
This settles the problem for the case of edge-colored digraphs. The case of edge-colored
graphs is different and more complex.
Theorem 3.2. Let A and B be permutation groups. Then, A × B ∈ GR, except for the
following cases:
(i) A×B /∈ DGR, that is, either A /∈ DGR or B /∈ DGR,
(ii) either every orbital of A ∈ GR is self-paired and B /∈ GR∪ {I2} or every orbital of
B ∈ GR is self-paired and A /∈ GR ∪ {I2},
(iii) A,B ∈ DGR \ (GR ∪ {I2}), and there exist a ∈ A∗ \A and b ∈ B∗ \B, such that
a transposes every pair of paired orbitals in A, and b transposes every pair of paired
orbitals in B.
Proof. We consider a few cases. An obvious consequence of Theorem 3.1 is the following
Corollary 3.3. Let A /∈ DGR and B be an arbitrary permutation group. Then, A × B /∈
GR.
Accordingly to this corollary, we will assume further that both the components of A×B
belongs to DGR. The next three lemmas deal with the case when one of the groups belongs
to GR or is equal to I2.
Lemma 3.4. Let A ∈ DGR \ (GR ∪ {I2}) and B ∈ GR. If every orbital of B is self-
paired, then A×B ̸∈ GR.
Proof. Denote A = (A, V ) and B = (B,W ). Let a ∈ A∗ \ A, and idB be the identity in
the permutation group B. Let e = {(v1, w1), (v2, w2)}, where v1, v2 ∈ V , w1, w2 ∈ W .
We show that the edges e and (a, idB)(e) have the same color. To this end it is enough to
prove that (a, idB)(e) belongs to the same 2∗-orbital of A×B as e.
264 Ars Math. Contemp. 21 (2021) #P2.06 / 259–269
If w1 = w2, then the statement holds by the fact that a preserves all 2∗-orbitals of A.
Assume v1 = v2. Since A ̸= I2, by Lemma 2.2, a preserves all orbits of A (in its action on
V ). Hence, there is a1 ∈ A such that a(v1) = a1(v1). We have,
(a, idB)({(v1, w1), (v1, w2)}) = {(a(v1), w1), (a(v1), w2)}
= (a1, idB)({(v1, w1), (v1, w2)}).
Thus, e and (a, idB)(e) belong to the same 2∗-orbital of A×B.
Now let v1 ̸= v2 and w1 ̸= w2. If the pair a((v1, v2)) belongs to the same orbital of
A as the pair (v1, v2), then there is a1 ∈ A such that a1(v1) = a(v1) and a1(v2) = a(v2).
Similarly as above, we have,
(a, idB)({(v1, w1), (v2, w2)}) = {(a(v1), w1), (a(v2), w2)}
= (a1, idB)({(v1, w1), (v2, w2)}).
Assume, finally, that v1 ̸= v2, w1 ̸= w2 and the pairs a((v1, v2)), (v1, v2) belong to
different orbitals of A. Since a ∈ A∗, we know that a preserves all 2∗-orbitals of A. This
implies that, the pairs a((v1, v2)) and (v2, v1) belong to the same orbital of A. Hence,
there is a1 ∈ A such that a1((v2, v1)) = a((v1, v2)). Moreover, since all orbitals of B are
self-paired, there is b ∈ B such that b((w1, w2)) = (w2, w1). Consequently,
(a, idB)(e) = {(a1(v2), b(w2)), (a1(v1), b(w1))} = (a1, b)(e).
Thus (a, idB)(e) and e belongs to the same 2∗-orbital of A×B, and consequently, (a, idB)
does not change the color of the edges.
It follows that (a, idB) ∈ Aut(G∗(A×B)) = (A×B)∗. Since a ∈ A∗ \A, (a, idB) /∈
A×B, and therefore A×B ̸= (A×B)∗, which completes the proof.
Lemma 3.5. Let A ∈ DGR\(GR∪{I2}) and let B ∈ GR have at least one not-self-paired
orbital. Then, A×B ∈ GR.
Proof. Let A = (A, V ) and B = (B,W ). We know, by Lemma 2.1(1), that Aut(G∗(A×
B)) ⊆ A∗ ×B. Therefore, every c ∈ Aut(G∗(A×B)) has the form (a, b), where a ∈ A∗
and b ∈ B. We show that, in fact, a always belongs to A. Assume, to the contrary, that
a ∈ A∗ \ A. In this case, since A ∈ DGR \ (GR ∪ {I2}), there is an (ordered) pair
(v1, v2), v1, v2 ∈ V such that a((v1, v2)) ̸= a1((v1, v2)), for every a1 ∈ A. Since B
has an orbital which is not-self-paired, there are w1, w2 ∈ W such that b((w1, w2)) ̸=
(w2, w1) for every b ∈ B. Now, observe that the edges (a, b)({(v1, w1), (v2, w2)}) and
{(v1, w1), (v2, w2)} belong to different 2∗-orbitals of A×B. Indeed, if the edges (a, b)({
(v1, w1), (v2, w2)}) and {(v1, w1), (v2, w2)} belong to the same 2∗-orbital of A×B, then
either there are a1 ∈ A and b1 ∈ B such that a((v1, v2)) = a1((v1, v2)) and b((w1, w2)) =
b1((w1, w2)) or there are a2 ∈ A and b2 ∈ B such that a((v1, v2)) = a2((v2, v1)) and
b((w1, w2)) = b2((w2, w1)). The first case is impossible by the assumption on a. In the
second case, we get b−12 b((w1, w2)) = (w2, w1), which contradicts the assumption. This
implies that E((a, b)({(v1, w1), (v2, w2)})) ̸= E({(v1, w1), (v2, w2)}), which contradicts
the fact that (a, b) ∈ Aut(G∗(A×B)). Consequently, we have Aut(G∗(A×B)) ⊆ A×B,
which completes the proof.
We summarize Lemma 3.4 and Lemma 3.5.
M. Grech: Decompositions of the automorphism groups of edge-colored graphs into the . . . 265
Corollary 3.6. Let A ∈ DGR \ (GR ∪ {I2}) and B ∈ GR. Then, A × B ∈ GR if and
only if there exists a non-self-paired orbital of B.
The following special case must be considered separately.
Lemma 3.7. Let B ∈ GR. Then, B × I2 ∈ GR.
Proof. By Lemma 2.1(1), Aut(G∗(B× I2)) is equal either to B× I2 or to B×S2. By our
general assumption B ̸= I1, hence, in G∗(B × I2), there is at least one edge of the form
{(v, 0), (w, 0)}, and being in different orbitals, it has a different color than {(v, 1), (w, 1)}.
Thus, Aut(G∗(B × I2)) = B × I2. Therefore, B × I2 ∈ GR.
This completes the description in all the cases where at least one of the components
belongs to GR.
The remaining case occurs where A,B ∈ (DGR \GR). We start with the following.
Lemma 3.8. Let A,B ∈ (DGR \ GR). If for every b ∈ B∗ there exists a pair of paired
orbitals O1 ̸= O2 of B such that b does not transpose O1 and O2, then A×B ∈ GR.
Proof. Let A = (A, V ) and B = (B,W ). Assume to the contrary that there exists (a, b) ∈
Aut(G∗(A×B))\(A×B).
First, assume that a ∈ A; then, b /∈ B. Since A ∈ (DGR \GR), there is an (ordered)
pair (v1, v2), where v1, v2 ∈ V , which belongs to a non-self paired orbital of A. Since
B ∈ DGR, there is an (ordered) pair (w1, w2) where w1, w2 ∈ W , for which there is no
b1 ∈ B such that b1((w1, w2)) = b((w1, w2)). We prove that the edge {(v1, w1), (v2, w2)}
belongs to a different 2∗-orbital than the edge (a, b)({(v1, w1), (v2, w2)}). Indeed, if the
edges (a, b)({(v1, w1), (v2, w2)}) and {(v1, w1), (v2, w2)} belong to the same 2∗-orbital,
then either there are a1 ∈ A and b1 ∈ B such that a((v1, v2)) = a1((v1, v2)) and
b((w1, w2)) = b1((w1, w2)) or there are a2 ∈ A and b2 ∈ B such that a((v1, v2)) =
a2((v2, v1)) and b((w1, w2)) = b2((w2, w1)). In the former, by assumption on b and
w1, w2, this is impossible. In the latter, since a ∈ A it is also impossible. Hence, the edges
(a, b)({(v1, w1), (v2, w2)}) and {(v1, w1), (v2, w2)} have different colors in G∗(A × B).
This contradicts the assumption that (a, b) ∈ Aut(G∗(A×B)).
Next, consider the case where a /∈ A. Since A ∈ DGR, there is an ordered pair
(v1, v2), where v1, v2 ∈ V , for which there is no permutation a1 ∈ A such that a1((v1, v2))
= a((v1, v2)). Let O1, O2 be orbital from the statement of the lemma. By assump-
tion, there are w1, w2 ∈ W such that {w1, w2} ∈ O1 and b((w1, w2)) ∈ O1. Thus,
b((w1, w2)) = b1((w1, w2)) for some b1 ∈ B. A similar proof as above shows that the
edge
(a, b)({(v1, w1), (v2, w2)}) = (a, b1)({(v1, w1), (v2, w2)})
belongs to a different 2∗-orbital than the edge {(v1, w1), (v2, w2)}. Again, this contradicts
the assumption that (a, b) ∈ Aut(G∗(A×B)).
Now, we consider the case where one of the groups is equal to I2.
Lemma 3.9. Let A ∈ (DGR \GR). Then, A× I2 ∈ GR.
Proof. Let A = (A, V ) and I2 = (I2, {w1, w2}). Assume to the contrary that there is
(a, b) ∈ Aut(G∗(A × I2)) \ (A × I2). Since, for any v1, v2, v3, v4 ∈ V , the edges
{(v1, w1), (v2, w1)} and {(v3, w2), (v4, w2)} have different colors, b = id. In the same
way as in the second case of the proof of the Lemma 3.8, we get a contradiction.
266 Ars Math. Contemp. 21 (2021) #P2.06 / 259–269
Now, we consider the last case.
Lemma 3.10. Let A,B ∈ DGR \ (GR∪ I2). If there exists a ∈ A∗ \A which transposes
all the pairs of the paired orbitals of A and there exists b ∈ B∗ \B which transposes all the
pairs of the paired orbitals of B, then A×B ̸∈ GR. Moreover, A×B is transitive.
Proof. Let A = (A, V ) and B = (B,W ). Since A ̸= I2 and B ̸= I2, by Lemma 2.2,
every permutation a ∈ A∗ \ A preserves the orbits of A (in its action on V ) and every
permutation b ∈ B∗ \ B preserves the orbits of B (in its action on W ). Hence, we ob-
tain immediately, under the assumptions on A and B, that the permutation groups A and
B have to be transitive. Consequently, for every a ∈ A∗, b ∈ B∗, v, v1, v2 ∈ V , and
w,w1, w2 ∈ W , the edge (a, b)({(v, w1), (v, w2)}) has the same color in G∗(A × B) as
the edge {(v, w1), (v, w2)}, and moreover, the edge (a, b)({(v1, w), (v2, w)}) has the same
color as the edge {(v1, w), (v1, w)}.
We choose a and b as in the statement of the lemma, and fix the elements v1 ̸= v2 ∈ V
and w1 ̸= w2 ∈ W . Since a and b preserves no non-self-paired orbital, the ordered
pair a((v1, v2)) belongs to the orbital of the ordered pair (v2, v1) and the ordered pair
b((w1, w2)) belongs to the orbital of the ordered pair (w2, w1). Hence, there are a1 ∈ A and
b1 ∈ B such that a((v1, v2)) = a1((v2, v1)) and b((w1, w2)) = b1((w2, w1)). Therefore,
we have
E((a, b)({(v1, w1), (v2, w2)})) = E({(a(v1), b(w1)), (a(v2), b(w2))})
= E({(a1(v2), b1(w2)), (a1(v1), b1(w1))})
= E((a1, b1)({(v1, w1), (v2, w2)}))
= E({(v1, w1), (v2, w2)}).
The vertices v1, v2, w1, and w2 are arbitrary. Hence, the permutation (a, b) preserves all
colors. Consequently, (a, b) ∈ Aut(G∗(A×B) \ (A×B)).
This exhausts all cases and ends the proof of the theorem.
4 Corollaries and problems
First, it is worth noting that for some subclasses the result may be stated in a nice simple
form. Since all intransitive permutation groups have a non-self-paired orbital, we have the
following.
Corollary 4.1. Let A ∈ DGR, and B ∈ GR be intransitive. Then, A×B ∈ GR.
Also, it is easy to observe that the only regular groups with all self-paired orbitals are
Sn2 , n ≥ 1. This implies that:
Corollary 4.2. Let A ∈ DGR, and B ∈ GR be regular. Then, A × B ∈ GR if and only
if B ̸= Sn2 , for every n.
Next, we give an alternative proof of the known fact, that was first observed in [22,
Example 3.15]
Corollary 4.3. Every regular permutation group belongs to DGR.
M. Grech: Decompositions of the automorphism groups of edge-colored graphs into the . . . 267
Proof. Let U be an nonsolvable regular group. Then, for every regular group A, the group
A × U is nonsolvable. By [5], we have A × U ∈ G(2) ⊆ DGR. By Theorem 3.1,
A ∈ DGR.
The next fact, it seems, was not recognized so far.
Corollary 4.4. Except for the abelian groups of exponent greater than two and generalized
dicyclic groups, all the finite regular permutation groups belong to the class GR.
Proof. Let A be an abelian group of exponent greater than two or a generalized dicyclic
group. It is proved in [5], that in such a case A /∈ G(2). The proof shows, in fact, that
A /∈ GR. Assume that A is not as those groups mentioned above. Then, it is well known
(see [5]) that A × S42 ∈ G(2). Since S42 ∈ GR and it has all orbitals self-paired, then by
Theorem 3.2 (ii), A ∈ GR.
Theorem 3.2 suggests a few open problems.
Problem 4.5. Describe the permutation groups that have all orbitals self-paired.
This does not seem to be an easy problem. Examples of groups whose all orbitals are
self-paired are Sn and their transitive products (direct product, wreath product, etc.). In
particular, all groups of the form Sk2 (the direct power) belong to this class. Yet, there are
other examples, like the automorphism groups of totally symmetric graphs described in
[11]. Note that if a permutation group A having all orbitals self-paired is an automorphism
group of a colored digraph D, A = Aut(D), then D is, in fact, an undirected colored
graph, and so A ∈ GR.
It would be also desirable to have a description of permutation groups with the property
given in Theorem 3.2(iii).
Problem 4.6. Describe all transitive permutation groups A having a permutation σ ∈ A∗ \
A transposing all pairs of paired orbitals.
We note that all regular abelian group of exponent greater than two and regular general-
ized dicyclic groups have this property. However, there are also many other examples. For
instance, the group A = ⟨(0, 1, 2, 3, 4, 5, 6), (1, 2, 4)(3, 6, 5)⟩ is one of them. This group is
a subgroup of Frobenius group F7 generated by translations and multiplication by 2 (which
is a permutation of order 3). This suggest the following.
Problem 4.7. Let A be a subgroup of the permutation group AGLn(p) generated by trans-
lations and ω2k, where ω is a generator of the the multiplicative group F ∗pn , and k divides
n. Moreover, let −1 be not quadratic in Fpn . Is it true that for each such group there is an
element a ∈ A∗ \A transposing all pairs of paired orbitals?
ORCID iDs
Mariusz Grech https://orcid.org/0000-0002-7328-8792
References
[1] L. Babai, Finite digraphs with given regular automorphism groups, Period. Math. Hungar. 11
(1980), 257–270, doi:10.1007/bf02107568.
268 Ars Math. Contemp. 21 (2021) #P2.06 / 259–269
[2] L. Babai, Automorphism groups, isomorphism, reconstruction, in: Handbook of combinatorics,
Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, pp. 1447–1540, 1995.
[3] P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Marušič and L. A.
Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc.
(2) 66 (2002), 325–333, doi:10.1112/s0024610702003484.
[4] M. Giudici, C. H. Li, P. Potočnik and C. E. Praeger, Homogeneous factorisations of graphs and
digraphs, European J. Combin. 27 (2006), 11–37, doi:10.1016/j.ejc.2004.08.003.
[5] C. D. Godsil, GRR’s for non solvable groups, in: Algebraic methods in graph theory, 1978 pp.
221–239.
[6] M. Grech, Direct products of automorphism groups of graphs, J. Graph Theory 62 (2009),
26–36, doi:10.1002/jgt.20385.
[7] M. Grech, The graphical complexity of direct products of permutation groups, J. Graph Theory
66 (2011), 303–318, doi:10.1002/jgt.20504.
[8] M. Grech, W. Imrich, A. D. Krystek and L. u. J. Wojakowski, Direct product of automorphism
groups of digraphs, Ars Math. Contemp. 17 (2019), 89–101, doi:10.26493/1855-3974.1498.
77b.
[9] M. Grech, A. Jeż and A. Kisielewicz, Graphical complexity of products of permutation groups,
Discrete Math. 308 (2008), 1142–1152, doi:10.1016/j.disc.2007.04.004.
[10] M. Grech and A. Kisielewicz, Direct product of automorphism groups of colored graphs, Dis-
crete Math. 283 (2004), 81–86, doi:10.1016/j.disc.2003.11.008.
[11] M. Grech and A. Kisielewicz, Totally symmetric colored graphs, J. Graph Theory 62 (2009),
329–345, doi:10.1002/jgt.20397.
[12] M. Grech and A. Kisielewicz, All totally symmetric colored graphs, Discrete Math. Theor.
Comput. Sci. 15 (2013), 133–145, doi:10.46298/dmtcs.630.
[13] W. Imrich, On products of graphs and regular groups, Israel J. Math. 11 (1972), 258–264,
doi:10.1007/bf02789317.
[14] A. Kisielewicz, Supergraphs and graphical complexity of permutation groups, Ars Combin. 101
(2011), 193–207.
[15] C. H. Li, T. K. Lim and C. E. Praeger, Homogeneous factorisations of complete graphs
with edge-transitive factors, J. Algebraic Combin. 29 (2009), 107–132, doi:10.1007/
s10801-008-0127-2.
[16] C. H. Li and C. E. Praeger, On partitioning the orbitals of a transitive permutation group, Trans.
Amer. Math. Soc. 355 (2003), 637–653, doi:10.1090/s0002-9947-02-03110-0.
[17] L. A. Nowitz and M. E. Watkins, Graphical regular representations of non-abelian groups.
I, II, Canadian J. Math. 24 (1972), 993–1008; ibid. 24 (1972), 1009–1018, doi:10.4153/
cjm-1972-101-5.
[18] W. Peisert, Direct product and uniqueness of automorphism groups of graphs, Discrete Math.
207 (1999), 189–197, doi:10.1016/s0012-365x(99)00044-8.
[19] G. Sabidussi, raph multiplication, Math. Z. 72 (1959), 446–457, doi:10.1007/bf01162967.
[20] M. E. Watkins, On the action of non-Abelian groups on graphs, J. Combinatorial Theory Ser.
B 11 (1971), 95–104, doi:10.1016/0095-8956(71)90019-0.
[21] M. E. Watkins and L. A. Nowitz, On graphical regular representations of direct products of
groups, Monatsh. Math. 76 (1972), 168–171, doi:10.1007/bf01298284.
M. Grech: Decompositions of the automorphism groups of edge-colored graphs into the . . . 269
[22] H. Wielandt, Permutation groups through invariant relations and invariant functions [83], in:
B. Huppert and H. Schneider (eds.), Volume 1 Group Theory, De Gruyter, pp. 237–296, 1969,
doi:10.1515/9783110863383.237.
[23] H. Wielandt, Permutation groups through invariant relation and invariant functions, in: B. Hup-
pert and H. Schneider (eds.), Mathematical works, vol. 1, Group theory, Walter de Gruyter Co.,
Berlin, pp. 237–266, 1994.
[24] H. P. Yap, Some Topics in Graph Theory, volume 108 of London Mathematical Society Lecture
Note Series, Cambridge University Press, Cambridge, 1986, doi:10.1017/cbo9780511662065.