ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 89-101
https://doi.org/10.26493/1855-3974.1498.77b
(Also available at http://amc-journal.eu)
Direct product of automorphism groups of
digraphs
Mariusz Grech *
Mathematical Institute, University of Wroclaw, pl. Grunwaldzki 2/4, 50-384 Wroclaw, Poland
Wilfried Imrich
Montanuniversität Leoben, Franz Josef-Straße 18, 8700 Leoben, Austria
Anna Dorota Krystek t
Faculty of Mathematics, Wroclaw University of Science and Technology, wyb. Wyspianskiego 27, 50-370 Wroclaw, Poland
Lukasz Jan Wojakowski í
Nokia Networks, ul. Lotnicza 12, 54-155 Wroclaw, Poland
Received 5 October 2017, accepted 24 January 2019, published online 22 June 2019
We study the direct product of automorphism groups of digraphs, where automorphism groups are considered as permutation groups acting on the sets of vertices. By a direct product of permutation groups (A, V) x (B, W) we mean the group (A x B, V x W) acting on the Cartesian product of the respective sets of vertices. We show that, except for the infinite family of permutation groups Sn x Sn, n > 2, and four other permutation groups, namely D4 x S2, D4 x D4, S4 x S2 x S2, and C3 x C3, the direct product of automorphism groups of two digraphs is itself the automorphism group of a digraph. In the course of the proof, for each set of conditions on the groups A and B that we consider, we indicate or build a specific digraph product that, when applied to the digraphs representing A and B, yields a digraph whose automorphism group is the direct product of A and B.
Keywords: Digraph, automorphism group, permutation group, direct product. Math. Subj. Class.: 05E18, 05C20, 20B25
*	Supported by the Polish National Science Centre grant No. 2012/07/B/ST1/03318.
tSponsored by the Polish National Science Centre grant No. 2012/05/B/ST1/00626 and by the travel grant PL 08/2016 of the 0EAD/DWM.ZWB.183.1.2016.
*	Corresponding author. Sponsored by the Polish National Science Centre grant No. 2012/05/B/ST1/00626 and by the travel grant PL 08/2016 of the 0EAD/DWM.ZWB.183.1.2016.
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
104
ArsMath. Contemp. 17 (2019) 90-114
The original problem of Konig [20], to describe finite abstract groups that are isomorphic to automorphism groups of simple graphs, quickly found an answer due to Frucht [5], namely, each finite group is isomorphic to the automorphism group of some simple graph. A related question, asking which permutation groups on a given set are automorphism groups of graphs on that set of vertices, proved to be much more difficult.
The simplest example of a permutation group that has no graph representation in this sense is the trivial group on two elements. Both simple graphs on two vertices admit the full permutation group S2 as automorphisms.
In the present paper, we deal with a generalization of the original problem. We study permutation group representability on directed simple graphs (digraphs). Note that the trivial group of the above example, while having no graph representation, obviously does have a digraph representation.
There are, however, groups that have neither graph nor digraph representations. The smallest example is the Klein four group S2 x S2 (even symmetries of a square), and that is despite the fact that both factors do have graph representations. This observation led us to study the representability of direct products of representable groups.
Our main result is Theorem 2.1 that says that, given two permutation groups (A, V) and (B, W) that have digraph representations, their direct product (A x B, V x W) also has a digraph representation, unless A x B is one of the four exceptional groups D4 x S2, D4xD4, S4xS2 x S2, Cf x Cf, or a member of the infinite family of groups Sn xSn,n > 2. It is a digraph counterpart of Theorem 2.10 of [8] by Grech for undirected graphs.
Although it might seem that this generalization should be straightforward, it turns out that we are in need, in addition to the conclusions of the aforementioned paper, of a whole collection of new techniques. The reason is that, as we have already seen in the introduction, there are plenty of permutation groups that are not the automorphism groups of a graph but are the automorphism groups of a digraph with at least one directed edge.
Research on the problem of representability of a permutation group A = (A, V) as the full automorphism group of a digraph (graph) G = (V, E) started with studies of regular permutation groups (see [15, 16, 18, 23, 24, 25, 29, 30], for instance). In particular, it was established that abelian groups and generalized dihedral groups have no simple graph representation. Moreover, 13 other groups with this property were found. The solution of the problem for undirected graphs was completed by Godsil [7] in 1979. He proved that with the exception of the groups mentioned above, all other regular permutation groups are automorphism groups of graphs. For digraphs, L. Babai [1] in 1980 used the result of Godsil, and proved that, except for the groups S|, Sf, S4, Cf and the eight element quaternion group Q, each regular permutation group is the automorphism group of a digraph.
The fact that all digraphs and graphs can be interpreted as complete digraphs (graphs) in which the edges and non-edges are distinguished by assigning them one of two colors provides motivation for working with edge-colored digraphs (or graphs) rather than with plain digraphs (graphs). This subject was introduced by H. Wielandt in [32], where permutation groups that are automorphism groups of edge-colored digraphs were called 2-closed, and those that are automorphism groups of edge-colored graphs were referred to as 2*-closed. In [19] Kisielewicz introduced the notion of graphical complexity of permutation groups and suggested studying products of permutation groups in this context. We
E-mail addresses: mariusz.grech@math.uni.wroc.pl (Mariusz Grech), imrich@unileoben.ac.at (Wilfried Imrich), anna.krystek@pwr.edu.pl (Anna Dorota Krystek), lukasz.wojakowski@nokia.com (Lukasz Jan Wojakowski)
M. Grech et al.: Direct product of automorphism groups of digraphs	91
denote by DGR(k) (GR(k)) the class of automorphism groups of k-edge-colored digraphs (graphs), and by DGR (GR), the union of all classes DGR(k) (GR(k)). A k-edge-colored digraph (graph) is a complete digraph (graph) with every edge colored in one of k colors. It is obvious that GR(k) C DGR(k), for every k. Note that the class DGR(2) (GR(2)) is the class of automorphism groups of digraphs (graphs).
The most general open question in this field is to find all permutation groups that belong to the class DGR. Another problem is to describe all the classes DGR(k). Several results on DGR(k) membership for basic classes of permutation groups are known, see for instance [1, 12, 34].
A closely connected topic is research on factorization of digraphs, see [3, 6,22] and the bibliography given there. The same problem as before is considered, but from a slightly different point of view. Special attention is devoted to homogeneous factorization of complete digraphs [12, 21].
Also, various products of automorphism groups of digraphs were considered, see for instance [10, 11, 14, 28, 31]. In particular, in [10], the direct product of automorphism groups of edge-colored digraphs was studied. One of the results, worked out there, is that, for k > 2, the direct product (A x B, V x W) of two permutation groups (A, V) and (B, W) from the class DGR(k) belongs to the class DGR(k + 1).
In [9] the study of the direct product was carried on and gave an improvement of the result from [10]. It was shown that for k > 3, the direct product of two groups from DGR(k) is either in DGR(k) or is equal to S3. The same holds for the case of automorphism groups of edge-colored graphs. The result of the present paper can be seen as an extension of the above result for the case k = 2.
1 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, 11, 33].
We recall the most important definitions. A digraph G is a pair (V, E), where V is the set of vertices. The set of oriented edges, E, is a subset of V x V \ {(v, v) : v e V} (the set of ordered pairs of different elements of V). By G we denote the complement of G. A complete digraph with n vertices is denoted by Kn.
An undirected edge is a pair {v, w} such that both (v, w) and (w, v) belong to E. By dG(v) we mean the number of undirected edges of the form {v, w}, w e V in a digraph G (the number of 1-neighbors of the vertex v). We define the number of non-neighbors (or 0-neighbors) of a vertex v by dG(v) = dG(v). If a digraph G is regular, then we denote these numbers dL(G) and d0(G), respectively. A directed edge is an edge (v, w) e E such that (w, v) e E. For every v e V, by dG (v), we denote the number of its forward-neighbors, that is, of directed edges of the form (v, w), w e V (with (w, v) e E).
In the case when a digraph G has no directed edges, we say that G is an undirected graph (a graph). For a digraph G we let s(G) denote the undirected graph (shadow graph) that is obtained from G by replacing all directed edges by undirected ones. We will also use the notion of weak neighbors of a vertex v in a digraph G, that is, of vertices that are neighbors of v in s(G). Similarly, a digraph is said to be weakly connected if s(G) is connected.
We define two products of digraphs Gi = (Vl,Ei) and G2 = (V2,E2). Their
104
ArsMath. Contemp. 17 (2019) 92-114
Cartesian product Gi □ G2 is a digraph Gi □ G2 = (V, E), where V = Vi x V2, and ((vi, v2), (wi, w2)) G E if either (vi, wi) G Ei and v2 = w2, or vi = wi and (v2, w2) G E2. We say that a digraph is prime if it is not the Cartesian product of two nontrivial digraphs. It is not hard to show that Cartesian multiplication of graphs is commutative, associative, and that Ki is a unit.
The second product Gi * G2 = (V, E), first studied by Watkins [28], is a digraph where V = Vi x V2 and ((vi, v2), (wi, w2)) G E if and only if either (vi, wi) G Ei and v2 = w2, or vi = wi and (v2, W2) G E2.
For a digraph G with vertex set V x W, the subdigraphs of G induced by sets V x {w} will be called rows, and the subdigraphs induced by sets {v} x W will be called columns. An edge that belongs neither to a row nor to a column will be called a slant edge. When G = Gi □ G2, for given v G V (G) and i G {1, 2} we will use the notation layer for the row or column (image of Gj) containing v and denote it Gf.
A permutation a of the set V is an automorphism of a digraph G = (V, E) (a G Aut (G)) if, for v, w G V, a pair (v, w) G E if and only if (a(v), a(w)) G E. It is obvious that Aut (G) is a group and that Aut (G) = Aut (G).
All groups considered here are groups of permutations. They are considered up to permutation group isomorphism. Sn denotes the full group of permutations of an n-element set. By Cn, n > 2, we denote the cyclic group on n elements (i.e. the group generated by the cycle (1, 2,..., n)). And finally, by Dn, n > 2, we denote the dihedral group acting on an n-element set (i.e. the group generated by (1, 2,..., n) and (1, n)(2, n -1)... ([n/2], n - [n/2] + 1)).
We define two kinds of products of permutation groups. Let A and B be permutation groups acting on the sets V and W, respectively. The direct product A x B is the permutation group consisting of the elements {(a, b) : a G A, b G B} acting on the set V x W as follows: (a, b)((v, w)) = (a(v), b(w)), for v G V, w G W. The group A x A is denoted A2. A wreath product A wr B acting imprimitively on the set V x W is the permutation group consisting of the elements {(a, bi,..., bn) : a G A, b G B, n = |V|} acting on the set V x W as follows: (a, bi,..., bn)(i, w) = (a(i), bj(w)), where i G {1,..., n} = V, w G W. (A acts on the set of columns, B acts on each column independently.)
The class of groups which are the automorphism groups of digraphs with at least one directed edge will be denoted by EDGR.
Lemma 1.1. Let G be a digraph and v, w, x, y G V (G), such that the only edges joining any two of them are (v, w), (y, x) G E (G) and {w, y}, {v, x} G E (G). Then, for every cartesian decomposition of the digraph G = Gi □ G2, there is an i G {1,2} such that all the arcs between v, w, x, y belong to Gf.
Proof. Without loss of generality assume that the layer Gf contains w. Vertex y can now be in the layer Gf = GW or in the layer GW. Assume the latter. Then, x has to be at the intersection of Gy and G2, as there are no slant arcs in G, but then the orientations of (v, w) and (y, x) are inconsistent with the definition of the cartesian product. Hence, vertex y must be in the layer Gf = G'f. Since the vertex x is a weak neighbor of both y and v which are in a single layer, it also must belong to that layer, because there are no slant arcs.	□
In contrast to the undirected case, where Imrich [14] found a short list of exceptional graphs for which both the graph and its complement are connected and not prime, for
M. Grech et al.: Direct product of automorphism groups of digraphs	93
digraphs with at least one directed edge there are no exceptions, as the following theorem
shows:
Theorem 1.2. For every digraph G with at least one directed edge either G or G is weakly connected and prime.
Proof. Assume the digraph G with at least one directed edge is not prime, that is G = Gi □ G2. We have to show that G is weakly connected and prime.
Let (v, w) = ((v1, v2), (w1, w2)) G E (G) be one of the directed edges of G. Without loss of generality, assume that (v1, w1) G E (G1) and v2 = w2. Since the cartesian decomposition is not trivial, there exists a vertex v2 G V (G2), v2 = v2. Then ((v1, v2), (w1, v2)) is also a directed edge in E(G). If between (v1, v2) and (v1, v2) there is no edge or there is a directed edge, then it is easy to see that the subdigraph of G induced by the vertices (w1, v2), (v1,v2), (w1,v2), (v1, v2) contains edges (directed or undirected) between every pair of vertices, and therefore belongs to a single layer of G. If there is an undirected edge between (v1,v2) and (v1,v2) then the same holds by Lemma 1.1. Now, all other vertices of G can be split into three categories according to their adjacence in G to the vertices (w1,v2), (v1, v2), (w1,v2), (v1, v2). First, those in G1 are neighbors of both (v1 , v2) and (w1,v2), and those in G^1'22^ are neighbors of both (v1,v2) and (w1, v2). Second, those in G2 are neighbors of both w and (w1, v2) and those in GW are neighbors of both v and (v1, v2). Third, all other vertices are neighbors of all four vertices (w1, v2), (v1, v2), (wb v2 ^ (vb v2).
Because a vertex can be a neighbor of two vertices in one and the same layer only if it also belongs to that layer, we conclude that all vertices in G belong to a single layer, so G is prime. It is easy to see that it also is weakly connected.
Assume now that G is prime and not weakly connected. Its complement G is connected. If G were not prime, then, by the previous paragraph, G = G would have to be weakly connected, contrary to assumption. Thus G is weakly connected and prime.	□
In what follows we need a result analogous to the Sabidussi-Vizing [26, 27] theorem about the automorphism group of the Cartesian product of connected coprime graphs. To prove it, we use a result on unique prime factorization of digraphs with respect to the Cartesian product. This result can be traced back to Feigenbaum [4], but for an easy proof in a more general setting we refer to the recent paper by Imrich and Peterin [17]:
Theorem 1.3. Every weakly connected digraph has a unique prime factor decomposition with respect to the Cartesian product.
We can now state our two simplified versions of the Sabidussi-Vizing theorem for digraphs.
Theorem 1.4. Let G, H be non-isomorphic weakly connected digraphs, where | V (G) | > |V (H )| and G is prime. Then Aut (G □ H) = Aut (G) x Aut (H).
Proof. It is clear that Aut (G) x Aut (H) c Aut (G □ H). We shall prove the opposite inclusion. To that end, it suffices to show that every a G Aut (G □ H) maps G-layers to G-layers and H-layers to H-layers in G □ H.
We know that Aut (G □ H) c Aut (s (G □ H)) and, in general, the factors of the shadowgraph s(G □ H) = s(G) □ s(H) need not be prime. Take a G Aut (G □ H). A G-layer in G □ H has the form G □ {h} for h G V (H). Consider s(G□ {h}), a
104
ArsMath. Contemp. 17 (2019) 94-114
cartesian product of subgraphs of s (G) and s (H). Using the terms defined in Chapter 6 of [13], it is a convex subgraph of the shadow graph s (G □ H), and so, by a corollary that leverages the convexity preserving property of automorphisms, obtained as a step in the proof of Theorem 6.8 therein (first paragraph on page 69), the image of s (G □ {h}) under the automorphism a is again a cartesian product of subgraphs of s (G) and s (H), that is, a(s(G□ {h})) = s(Gi) □ s (Hi), where Gi C G and Hi C H. But, since the vertex sets of the shadows are the same as those of the digraphs, we also have that a(G□ {h}) = G1 □ H1. Suppose |V (G1)| = 1, that would imply that H1 = H with |V (H)| = |V (G)| and that G is isomorphic to H, which is contrary to assumption. Now suppose that 1 < | V (G1) | < | V (G)|. This would imply that the digraph G has a nontrivial cartesian product decomposition, which is also contrary to assumption. We are, thus, left with the case | V (G1) | = | V (G) |, which proves that a maps G-layers to G-layers.
Because we have no slant arcs and H is weakly conected this means that a maps H-layers into H-layers.	□
Theorem 1.5. Let G be a weakly connected, prime digraph with at least one directed edge. Let H be an undirected and connected graph. Then Aut (G □ H) = Aut (G) x Aut (H).
Proof. Similarly as above, we get that a(s(G□ {h})) = s(G1) □ s(H1). We do not assume that the digraph G has at least as many vertices as H, so we need to exclude the case |V (G1)| = 1 differently. Here this would imply that G is a subgraph of H, but this is not possible as G has a directed edge while H does not. The conclusion follows as above.	□
The following proposition is modelled on an observation made in the proof of Theorem 6 of Watkins [28]:
Proposition 1.6. Let G1 = (V1, E1) and G2 = (V2, E2) be digraphs where G2 is weakly connected. Suppose that every automorphism a of the digraph G = G1 * G2 maps rows onto rows. Then Aut (G) = Aut (G1) x Aut (G2).
Proof. Let w1 and w2 be weak neighbors in G2 and let v e V1 be arbitrarily chosen. Write
a(v, wj) = (a1(v, wj), a2(v, Wj)). Since rows are mapped onto rows, a2 does not depend on v. Hence, a2 e Aut (G2).
By the definition of the *-product, (v,W2) is the only vertex in G^2) that is not weakly adjacent to (v,w1). Hence a(v,w2) = (a1(v, w2), a2(w2)) is the only vertex in Ga(v,w2) that is not weakly adjacent to (a1(v, w1), a2(w1)), so a1 (v, w1) must be equal to a1(v, w2). By the weak connectivity of G2 this means that a1 only depends on v. It is easily seen that it is an automorphism of G1. Thus, for any (v, w) e V(G) we conclude that a(v, w) = (a1(v), a2(w)), where a1, a2 are a automorphisms of G1, resp. G2. □
2 Main result
The following theorem settles the problem when the direct product of automorphism groups of digraphs is an automorphism group of a digraph.
Theorem 2.1. Let A, B e DGR(2). Then A x B e DGR(2), unless A x B is D4 x S2, D4 x D4, S4 x S2 x S2, C3 x C3, or one of the groups Sn x Sn, n > 2.
M. Grech et al.: Direct product of automorphism groups of digraphs	95
The proof is broken up into a series of lemmas. Let us note first that we are given permutation groups A = (A, VA), B = (B, VB) and graphs GA = (VA, EA), GB = (VB, EB), where Aut (GA) = A and Aut (GB) = B. Since Aut (G) = Aut (G) for any G we may assume without loss of generality that both GA and GB are weakly connected. Moreover, by Theorem 1.2 we may also assume that they are prime if they have at least one directed edge.
We begin by extending Theorem 2.10 of [8] by Grech for undirected graphs to directed graphs.
Lemma 2.2. Let A, B G GR(2). Then A x B G DGR(2) if and only if A x B G GR(2).
Proof. By Theorem 2.10 of [8], A x B G GR(2), unless A x B is D4 x S2, D4 x D4, S4 x S2 x S2 or Sn x Sn, for n > 2. In the exceptional cases the pair (v2, v1) belongs to the orbit of the pair (vi, v2) in the natural action of the group (A x B, V) on pairs of elements of V. Thus, every digraph G such that A x B C Aut (G) has to be an undirected graph. Hence, in all the cases, A x B g DGR(2) would imply A x B G GR(2). Consequently, in the exceptional cases, A x B G DGR(2).	□
Notice that this takes care of all exceptional groups of Theorem 2.1 that are different from C3 x C3. The proof also shows that in what follows it suffices to consider only the cases where either A or B admits a digraph representation with at least one directed edge. We can thus assume without loss of generality that A g EDGR.
Lemma 2.3. Assume that A, B are non-isomorphic groups, where A G EDGR and B G DGR(2). Then Aut (GA □ GB) = Aut (GA) x Aut (GB)
Proof. As noted above, GA and GB can be chosen to be weakly connected, the complement being taken if necessary, with GA being prime. Then, if B G EDGR so that GB can also be chosen to be prime, the proof follows from Theorem 1.4, and from Theorem 1.5 otherwise.	□
This means that we can assume that B = A. Moreover, if we are able to find two non-isomorphic weakly connected digraphs, at least one of which is prime, with the same automorphism group A, then Theorem 1.4 also gives us a positive answer.
It therefore remains to consider the case A x A, where A is the automorphism group of a weakly connected prime digraph GA with at least one directed edge. In other words, we can assume that A G EDGR and that GA is prime.
Lemma 2.4. Let A G EDGR with prime GA. If A is intransitive, then A x A G DGR(2).
Proof. We consider two copies Gr = (Vr, Er) and Gc = (Vc, Ec) of GA and will define a digraph G = (Vr x Vc, E) such that Aut (G) = A x A. We call Gr the row copy and Gc the column copy of GA.
Since A is intransitive, GA = K| Va |. Let W C Vc be one of the orbits of A in its action on Gc. The edge set E of the digraph G = (Vr x Vc, E) is then defined as the set of all pairs ((vr, vc), (wr, wc)) satisfying one of the following conditions:
(a)	(vc, wc) G Ec and vr = wr;
(b)	vc = wc and
• either vc g W
104
ArsMath. Contemp. 17 (2019) 96-114
• or vc G W, and (vr, wr) G Er.
Notice that there are no slant edges and that the subgraphs induced by the columns {vr } x Vc are isomorphic to GA, whereas the the subgraphs induced by the rows Vr x {vc} are isomorphic to K|Va| if vc G W, otherwise they are isomorphic to GA.
In other words, Vr x W induces the Cartesian product K|Va| □ (W}, where (W} denotes the subgraph of GA induced by W, and Vr x {Vc \ W} induces GA □ (Vc \ W}.
It is easy to see that A x A C Aut (G). We have to prove the converse. To that end it suffices to show that Aut (G) maps rows onto rows and columns onto columns.
Consider a row Vr x {vc}, where vc G W. The row induces a complete subgraph. Because we have no slant edges, automorphisms can only map it into rows or columns. As all rows and columns have the same number of vertices and since GA = K| Va |, it can only be mapped onto a Vr x {wc}, where wc g W.
We will now prove that automorphisms of G map columns onto columns. Pick a vc G W to single out one of the rows of W, and let (wr, wc) be any vertex of G. As there are no slant edges in G, the paths realizing the weak distance of (wr, wc) to points (vr, vc) in the chosen row will be built of column edges and row edges. By analogy to the reasoning behind the distance formula for the cartesian product, the column edges of any such path projected onto the column graph Gc will form a weak path from wc to vc in Gc, just as in a cartesian product, but the row edges can go through regular rows or through K| Va | rows. When vr equals wr, row edges are eliminated. That means that given a vertex (wr, wc) there is a unique vertex in the chosen row Vr x {vc}, to which weak distance p in G is minimal, this unique vertex (wr, vc) is in the same column as (wr, wc) and is unique in the above sense for all vertices (wr, wc) of that column.
Consider now an automorphism a G Aut (G). We already know that it will map the row Vr x {vc} onto some other row Vr x {xc}. If the vertices (xr, xc) = a(wr, vc) and (yr, yc) = a(wr, wc) were in different columns, that is if xr = yr, there would be a vertex (yr, xc) in row xc closest to (yr, yc) and different than (xr, xc):
while after having applied a-1 on both sides we would get
p ((wr, Vc), (wr ,WC)) > P ((w^, Vc), (wr ,WC)) ,
with w^, = wr because of xr = yr, but that cannot be true. Hence, any automorphism maps columns onto columns, as vertices of G follow their closest vertices in the chosen row.
Since column edges are mapped by automorphisms onto column edges, row edges are mapped only to row edges, thus, the only way the image of a row can preserve its weak connectedness is for automorphisms to map entire rows onto entire rows.	□
Lemma 2.5. Let A G EDGR with prime GA. If A is transitive and | VA | < 4, then A x A G EDGR unless A = C3.
Proof. The group A is one of C3 and C4. By a result of Babai [1], C3 x C3 G EDGR. C4 x C4 G EDGR by Theorem 1.4 for GC4 and GC4.	□
Observe that this takes care of the last exceptional case of Theorem 2.1.
Lemma 2.6. Let A G EDGR with prime GA, where A is transitive and |VA| > 4. If GA is weakly connected, then A x A G EDGR.
M. Grech et al.: Direct product of automorphism groups of digraphs
97
Proof. Denote n = |VA|. Since the graph GA is weakly connected, we only need to consider the case GA = GA (otherwise the conclusion follows from Theorem 1.4). This implies that d0(GA) = dQ(GA). Because GA is not undirected, we infer that 2df (GA) > 1. Then d0(GA) + d1(GA) + 2df (GA) = n - 1 implies 2d1(GA) = 2d0(GA) < n - 2.
We shall now prove that the graph G = Gr * Gc, where Gr = (Vr, Er) and Gc = (Vc, Ec) are copies of GA, has the property Aut (G) = A x A. To this end, we will show that every undirected edge that is contained in a row is mapped, under the action of Aut (G), onto an undirected edge which is contained in a row, and that the same is true for directed edges.
Let us compare the numbers of the common 1 -neighbors of the ends of an undirected edge which is contained in a row, with the same number for the ends of an undirected slant edge. Denote the ends of the edge e by (vr, vc) and (wr, wc). If e is contained in a row (vc = wc), then the common 1-neighbors of (vr, vc) and (wr, wc) are those contained in that row, together with all but two vertices in rows corresponding to 1-neighbors of vc = wc in Gc, hence their number is equal to
NQr (vr,wr ) + (n - 2)d1(Gc),	(2.1)
where NQ (vr, wr) is the number of common 1-neighbors of the vertices vr and wr (in Gr). If e is a slant edge, the common 1-neighbors of (vr,vc) and (wr,wc) are the 1-neighbors contained in both rows (excluding the vertex directly in front of the other end if it also is such a 1-neighbor), together with all but two vertices in rows corresponding to common 1-neighbors of both vc and wc in Gc. Thus, their number is
(n - 2)Nlc (vc, wc) + 2d1(Gr) - 2S,	(2.2)
where NQ (vc,wc) is the number of common 1-neighbors of the vertices vc and wc (in Gc), and S°G {0,1}.
The assumption that the numbers (2.1) and (2.2) are equal, implies
(n - 2)(dQ(Gc) - NQc (vc,wc)) + NQr (vr,wr) - 2dQ(Gr) + 2S = 0.
Since dQ(Gc) > NQc (vc,w c) and 2dQ(Gr) < n-2, it cannot be true. Hence, an undirected edge which is contained in a row cannot be mapped onto a slant undirected edge. Since there are no undirected edges in columns of a *-product, the set of the undirected edges that are contained in the rows is preserved by automorphisms.
We continue with a similar calculation for directed edges. Let e be a directed edge with ends as above. If e is contained in a row, then by similar reasoning as in the undirected case, the number of common forward-neighbors of (vr, vc) and (wr, wc) equals
Nf (vr,wr) + (n - 2)df (Gc),	(2.3)
where Nf (vr, wr) is the number of common forward-neighbors of the vertices vr and wr (in Gr). If e is a slant edge, then this number is
(n - 2)Nf (vc, wc) + (Gr) - S,	(2.4)
where Nf (vc, wc) is the number of common forward-neighbors of the vertices vc and wc (in Gc), and S G {0,1}.
104
ArsMath. Contemp. 17 (2019) 98-114
If it were possible for an automorphism from Aut (G) to map a directed slant edge onto a directed row edge, the numbers (2.3) and (2.4) would need to be the same, which would imply
(n - 2)(dG (Gc) - NfGc (vc, wc)) + Nf (vr, wr) - dG (Gr) + S = 0. (2.5)
If e = ((vr, vc), (wr, wc)) is a directed slant edge, then (vc, wc) is a directed edge of Gc. The equality dG (Gc) = Nf (vc, wc) would then imply that the set of forward-neighbors of each of the vertices vc and wc be identical, but this cannot be true, since wc is a forward-neighbor of vc but not of itself. Hence, dG(Gc) > Nf (vc, wc). Note that since A is transitive, every vertex has as many backward neighbours as forward neighbours. Therefore since n > 4, we infer dG (Gr) < n - 2. Thus, equation (2.5) cannot be true and the set of directed edges that are contained in rows is preserved by automorphisms also in this case. Because GA is weakly connected, it follows by Proposition 1.6 that Aut (G) = A x A. □
Lemma 2.7. Let A G EDGR, with prime GA, be transitive. If GA is disconnected, then A x A G EDGR.
Proof. We first consider the structure of GA. Because A is transitive, the subgraphs of Ga induced by the vertices belonging to common weakly connected components of GA are isomorphic, so VA = W' x W, where the weakly connected components of GA are grouped as columns, with column size s = | W | = n/t, where t = | W'| > 2 is the number of weakly connected components of GA. Thus, the group A acts on the set of columns as St, and on every column independently as some Ai, hence A = St wr Ai. Since there are no edges between columns of GA we infer that (v, w) G E(GA) if v and w belong to different columns. Because A is transitive, and GA is not undirected, we conclude that either s > 4 or A1 = C3.
In the latter case, we define G = Gr * Gc, where both Gr and Gc are isomorphic to Ga. Then, it is easy to see that the ends of the undirected edges in the rows have common forward-neighbors, and the ends of the undirected slant edges do not. Since the undirected edges in rows form spanning connected subgraphs of the rows, Aut (G) maps rows onto rows. By Proposition 1.6 we conclude that Aut (G) = A x B.
In the case s > 4, we define a graph G = (Vr x Vc, E) such that ((vr, vc), (wr, wc)) is in E if either vc = wc and (vr, wr) G E(Gr) or (vc, wc) G E(Gc), vr = wr, and the vertices vr and wr belong to the same weakly connected component in Gr.
If a connected graph H has a disconnected complement, then the subgraphs of H that are induced by the vertices of the weakly connected components of H are sometimes called Zykov components of H. Our graph G thus consists of t copies of the R * Gc, where R is a Zykov-component of Gr, and the row-edges that are not in a copy of R * Gc. We say these row-edges are of type Q.
We wish to show that Aut (G) = A x A. It is easy to check that A x A C Aut (G). We have to prove that the converse also holds. To this end, we count the common weak neighbors of the ends of the edges that are contained in a row. These edges have the form {(vr, vc), (wr,wc)}, where vc = wc. If vr and wr do not belong to the same Zykov component in Gr, then these edges are of type Q. The number of common weak neighbors of the endpoints of edges of type Q is
x = (t - 2)s + 2dW,
(2.6)
M. Grech et al.: Direct product of automorphism groups of digraphs	99
where dw is the number of those weak neighbors of a vertex in Gr that belong to the same Zykov component of Gr. (The notation dW is chosen, because all Zykov components are isomorphic to W as defined in the beginning of the proof.) For row-edges that are not of type Q the number of common weak neighbors of their endpoints is
y = (t - 1)s + NW(vr, Wr) + (s - 2) ((t - 1)s + dw),	(2.7)
where Nw (vr, wr) is the number of the common weak neighbors of the vertices vr and wr in their Zykov component. Since x < (t - 1)s + dw, it is obvious that x < y.
Moreover, the number of common weak neighbors of the ends of the slant edges of G
is
2(dw - e) + (s - 2)Nw(vc, wc) + (s - 2)(t - 1)s
for some e G {0,1} if the endpoints of {vc,wc} G E(Gc) belong to the same Zykov component of Gc, and
2(dw - e) + 2(s - 2)dw + (s - 2)(t - 2)s
for some e G {0,1} if the endpoints of {vc, wc} G E(Gc) belong to different Zykov components of Gc. It is easy to see that under our assumptions both numbers are strictly greater than x. Observe that the graph G has no edges that are contained in its columns.
This calculation implies that Aut (G) preserves the set of edges of type Q. Since these edges form spanning subgraphs for all graphs induced by the rows of G, every a G Aut (G) maps rows of G onto rows. Moreover, a maps any copy of a Zykov component of Gr that is contained in a row in G onto a copy of a Zykov component of Gr that is contained in the image of that row.
To complete the proof, we have to show that each column of G is mapped onto a column. If we remove edges of type Q we are left with t identical subgraphs R * Gc where i = 1,..., t. As any automorphim a of G maps rows into rows, it also maps subrows of the form R x {vc} into subrows of the same form Rj x {a(vc)}.
Note that by assumption R has s > 4 vertices. Thus, every R * Gc is weakly connected. From this we infer that automorphisms of G map entire subgraphs R * Gc onto entire subgraphs Rj * Gc, as in G there are no slant edges between vertices belonging to different Zykov components.
Call subrows Rj x {vc} and Rj x {wc} of G adjacent if there is an edge or directed edge between some vertices of them, that is, when there is an edge or a directed edge between vc and wc in Gc and i = j.
If Rj x {vc} and Rj x {wc} are adjacent, so are Rj x {a(vc)} and Rj x {a(wc)} and the non-edges between vertices of the subrows are mapped to non-edges between vertices of the images of the subrows. But the non-edges of adjacent subrows span subgraphs that are isomorphic to copies of Gc and whose vertex sets are the columns. Therefore, columns of G are mapped onto columns.	□
This also completes the proof of the main theorem. References
[1] L. Babai, Finite digraphs with given regular automorphism groups, Period. Math. Hung. 11 (1980), 257-270, doi:10.1007/bf02107568.
104
ArsMath. Contemp. 17 (2019) 100-114
[2]	L. Babai, Automorphism groups, isomorphism, reconstruction, in: R. L. Graham, M. Grotschel and L. Lovdsz (eds.), Handbook of Combinatorics, Volume 2, Elsevier, Amsterdam, pp. 14471540, 1995.
[3]	A. Bonisoli and D. Labbate, One-factorizations of complete graphs with vertex-regular automorphism groups, J. Combin. Des. 10 (2002), 1-16, doi:10.1002/jcd.1025.
[4]	J. Feigenbaum, Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time, Discrete Appl. Math. 15 (1986), 105-110, doi:10.1016/ 0166-218x(86)90023-5.
[5]	R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1939), 239-250, http://www.numdam.org/item?id=CM_193 9_6_239_0.
[6]	M. Giudici, C. H. Li, P. Potocnik 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.
[7]	C. D. Godsil, GRRs for nonsolvable groups, in: L. Lovdsz and V. T. S6s (eds.), Algebraic Methods in Graph Theory, Volume I, North-Holland, Amsterdam, volume 25 of Colloquia Mathematica Societatis Janos Bolyai, pp. 221-239, 1981, papers from the conference held in Szeged, August 24-31, 1978.
[8]	M. Grech, Direct products of automorphism groups of graphs, J. Graph Theory 62 (2009), 26-36, doi:10.1002/jgt.20385.
[9]	M. Grech, The graphical complexity of direct products of permutation groups, J. Graph Theory 66 (2011), 303-318, doi:10.1002/jgt.20504.
[10]	M. Grech, A. Jez and A. Kisielewicz, Graphical complexity of products of permutation groups, Discrete Math. 308 (2008), 1142-1152, doi:10.1016/j.disc.2007.04.004.
[11]	M. Grech and A. Kisielewicz, Direct product of automorphism groups of colored graphs, Discrete Math. 283 (2004), 81-86, doi:10.1016/j.disc.2003.11.008.
[12]	M. Grech and A. Kisielewicz, Totally symmetric colored graphs, J. Graph Theory 62 (2009), 329-345, doi:10.1002/jgt.20397.
[13]	R. Hammack, W. Imrich and S. Klavzar, Handbook of Product Graphs, Discrete Mathematics and its Applications, CRC Press, Boca Raton, Florida, 2nd edition, 2011, doi:10.1201/b10959.
[14]	W. Imrich, On products of graphs and regular groups, Isr. J. Math. 11 (1972), 258-264, doi: 10.1007/bf02789317.
[15]	W. Imrich, On graphical regular representations of groups, in: A. Hajnal, R. Rado and V. T. S6s (eds.), Infinite and Finite Sets, Volume II, North-Holland, Amsterdam, volume 10 of Colloquia Mathematica Societatis Janos Bolyai, pp. 905-925, 1975, dedicated to Paul ErdCs on his 60th birthday, proceedings of a colloquium held at Keszthely, June 25 - July 1, 1973.
[16]	W. Imrich, Graphical regular representations of groups of odd order, in: A. Hajnal and V. T. S6s (eds.), Combinatorics, Volume II, North-Holland, Amsterdam, volume 18 of Colloquia Mathematica Societatis Janos Bolyai, pp. 611-621, 1978, proceedings of the 5th Hungarian Colloquium held at Keszthely, June 28 - July 3, 1976.
[17]	W. Imrich and I. Peterin, Cartesian products of directed graphs with loops, Discrete Math. 341 (2018), 1336-1343, doi:10.1016/j.disc.2018.01.021.
[18]	W. Imrich and M. E. Watkins, On graphical regular representations of cyclic extensions of groups, Pac. J. Math. 55 (1974), 461-477, http://projecteuclid.org/euclid. pjm/1102910980.
[19]	A. Kisielewicz, Supergraphs and graphical complexity of permutation groups, Ars Combin. 101 (2011), 193-207.
M. Grech et al.: Direct product of automorphism groups of digraphs
101
[20]	D. Konig, Theory of Finite and Infinite Graphs, Birkhauser, Boston, Massachusetts, 1990, doi: 10.1007/978-1-4684- 8971- 2.
[21]	C. H. Li, T. K. Lim and C. E. Praeger, Homogeneous factorisations of complete graphs with edge-transitive factors, J. Algebr. Combin. 29 (2009), 107-132, doi:10.1007/ s10801-008-0127-2.
[22]	C. H. Li and C. E. Praeger, On partitioning the orbitals of a transitive permutation group, Trans. Am. Math Soc. 355 (2003), 637-653, doi:10.1090/s0002-9947-02-03110-0.
[23]	L. A. Nowitz, On the non-existence of graphs with transitive generalized dicyclic groups, J. Comb. Theory 4 (1968), 49-51, doi:10.1016/s0021-9800(68)80086-9.
[24]	L. A. Nowitz and M. E. Watkins, Graphical regular representations of non-abelian groups, I, Canad. J. Math 24 (1972), 993-1008, doi:10.4153/cjm-1972-101-5.
[25]	L. A. Nowitz and M. E. Watkins, Graphical regular representations of non-abelian groups, II, Canad. J. Math 24 (1972), 1009-1018, doi:10.4153/cjm-1972-102-3.
[26]	G. Sabidussi, Graph multiplication, Math Z. 72 (1959/60), 446-457, doi:10.1007/bf01162967.
[27]	V. G. Vizing, The cartesian product of graphs (in Russian), Vychisl. Sistemy 9 (1963), 30-43.
[28]	M. E. Watkins, On the action of non-Abelian groups on graphs, J. Comb. Theory Ser. B 11 (1971), 95-104, doi:10.1016/0095-8956(71)90019-0.
[29]	M. E. Watkins, On graphical regular representations of Cn x Q, in: Y. Alavi, D. R. Lick and
A.	T. White (eds.), Graph Theory and Applications, Springer, Berlin, volume 303 of Lecture Notes in Mathematics, pp. 305-311, 1972, doi:10.1007/bfb0067383, dedicated to the memory of J. W. T. Youngs, proceedings of the Conference at Western Michigan University, Kalamazoo, Michigan, May 10 - 13, 1972.
[30]	M. E. Watkins, Graphical regular representations of alternating, symmetric, and miscellaneous small groups, Aequat. Math. 11 (1974), 40-50, doi:10.1007/bf01837731.
[31]	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.
[32]	H. Wielandt, Permutation groups through invariant relations and invariant functions, in:
B.	Huppert and H. Schneider (eds.), Group Theory, Walter de Gruyter, Berlin, volume 1 of Mathematische Werke/Mathematical Works, pp. 237-297, 1994.
[33]	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.
[34]	A. Z. Zelikovsky, The Konig problem for Abelian permutation groups, Proc. Natl. Acad. Sci. Belarus, Ser. Phys.-Math Sci. 5 (1989), 34-39.