¿^creative ^commor ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 19 (2020) 325-335 https://doi.org/10.26493/1855-3974.2122.1e2 (Also available at http://amc-journal.eu) On generalized truncations of complete graphs* XueWang , Fu-Gang Yin , Jin-Xin Zhou Mathematics, Beijing Jiaotong University, Beijing, 100044, P.R. China Received 21 September 2019, accepted 23 August 2020, published online 20 November 2020 Abstract For a k-regular graph r and a graph Y of order k, a generalized truncation of r by Y is constructed by replacing each vertex of r with a copy of Y. E. Eiben, R. Jajcay and P. Sparl introduced a method for constructing vertex-transitive generalized truncations. For convenience, we call a graph obtained by using Eiben et al.'s method a special generalized truncation. In their paper, Eiben et al. proposed a problem to classify special generalized truncations of a complete graph Kn by a cycle of length n -1. In this paper, we completely solve this problem by demonstrating that with the exception of n = 6, every special generalized truncation of a complete graph Kn by a cycle of length n - 1 is a Cayley graph of AGL(1, n) where n is a prime power. Moreover, the full automorphism groups of all these graphs and the isomorphisms among them are determined. Keywords: Truncation, vertex-transitive, Cayley graph, automorphism group. Math. Subj. Class. (2020): 05C25, 20B25 1 Introduction In [6], the symmetry properties of graphs constructed by using the generalized truncations was investigated. In particular, a method for constructing vertex-transitive generalized truncations was proposed (see [6, Construction 4.1 and Theorem 5.1]), and this method was used to construct vertex-transitive generalized truncations of a complete graph Kn by a cycle of length n - 1 for some small values of n. The vertex-transitive generalized truncations of a complete graph Kn by a graph Y in context of [6, Theorem 5.1] can be defined as follows. Let Kn be a complete graph of order n with n > 4, and let V (Kn) = [v\, v2,..., vn}. Let G be an arc-transitive group of automorphisms of Kn. Then G acts 2-transitively * The authors also thank the anonymous referee for the valuable comments and suggestions. This work was partially supported by the National Natural Science Foundation of China (grant numbers 11671030 and 12071023). 1 Corresponding author. E-mail addresses: xuewang@bjtu.edu.cn (XueWang), 18118010@bjtu.edu.cn (Fu-Gang Yin), jxzhou@bjtu.edu.cn (Jin-Xin Zhou) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 326 Ars Math. Contemp. 19 (2020) 189-208 on V(Kn). Let v = vi, and let be a union of orbits of the stabilizer Gv acting on {{x, y} | x = y, x, y € V(Kn) \ {v}}. Let T be the graph with vertex set {v2, v3,..., vn} and edge set . For each u € V(Kn), let Vu = {(u,w) | w € V(Kn) \ {u}}. The special generalized truncation of Kn by T, denoted by T(Kn, G, T), is the graph with the vertex set |JueVVu, and the adjacency relation in which a vertex (u, w) is adjacent to the vertex (w, u) and to all the vertices (u, w') for which there exists a g € G with the property ug = v and {w, w'}g € . Based on the analysis of special generalized truncations of a complete graph Kn by a cycle of length n - 1 for some small values of n, the authors of [6] proposed the following problem. Problem 1.1 ([6, Problem 5.4]). Classify the special generalized truncations of Kn (n > 4) by a cycle of length n - 1 . The main purpose of this paper is to give a solution of this problem. Before stating the main result of this paper, we first set some notation. For a positive integer n, we denote by Zn the cyclic group of order n, and by D2n the dihedral group of order 2n. Let Z^ be the multiplicative group of units mod n (Z£ consists of all positive integers less than n and coprime to n). Also we use An and Sn respectively to denote the alternating and symmetric groups of degree n. For two groups M and N, N xi M denotes a semidirect product of N by M. For a group G, the automorphism group of G and the socle of G will be represented by Aut(G) and soc(G), respectively. For a graph r we denote by V(r), E(r), A(r) and Aut(r) the vertex set, edge set, arc set and full automorphism group of r, respectively. A graph r is said to be vertex-transitive (resp. arc-transitive (or symmetric)) if Aut(r) acts transitively on V(r) (resp. A(r)). Cayley graphs form an important class of vertex-transitive graphs. Given a finite group G and an inverse closed subset S C G \ {1}, the Cayley graph Cay(G, S) on G with respect to S is the graph with vertex set G and edge set {{g, sg} | g € G, s € S}. Finally, we use Kn and Cn respectively to denote the complete graph and cycle with n vertices. Let p be a prime and e a positive integer. Let GF(pe) be the Galois field of order pe and let x be a primitive root of GF(pe). Then AGL(1,pe) = {aXi: z ^ zx! + z', Vz € GF(pe) | i € Zpe-1,z' € GF(pe)}, and AGL(1,pe) is a 2-transitive permutation group on GF(pe). Let H = {a1jZ/: z ^ z + z', Vz € GF(pe) | z' € GF(pe)}, K = 0 : z ^ zx®, Vz € GF(pe) | i € Zpe-1}. Then H is regular on GF(pe) and the point stabilizer AGL(1,pe)0 of the zero element 0 of GF(pe) is K. So AGL(1,pe) = H x K. Construction 1.2. Let z' be a non-zero element of GF(pe). For each i € Zpe-1 with i < £er1, let Kpe = Cay(AGL(1,pe), {a_1,z', «^,0, «x-,o}) (p > 2), K2e = Cay(AGL(1, 2e), {aM,, aai,o, aa-i,o}) (p = 2). X. Wang, F.-G. Yin and J.-X. Zhou: On generalized truncations of complete graphs 327 Remark 1.3. Let z', z" be two non-zero elements of GF(pe). There exists xj e GF(pe) \ {0} such that z'xj = z''. So [a~i,z>,axi,o, ax-i = {a_i,z", «x\0, ax—,0} (p > 2), {«1,z' ,«xi,0,«x-i ,0}"xj,° = {«1,z" ,«xi,0,«x-i,0} (p = 2). It follows that Cay(AGL(1,pe), {a_M',«x>,0, ^-¿,0}) = Cay(AGL(1,pe), {a_i,z",0^,0, ax-,0}) (p > 2), Cay(AGL(1, 2e), {«i,z-, «x\0, ^-¿,0}) = Cay(AGL(1, 2e), {aM„, «x-,0, «^-,0}) (p = 2). In view of this fact, up to graph isomorphism, Kp- is independent of the choice of z'. The following is the main result of this paper. Theorem 1.4. Let Kn be a special generalized truncation of Kn (n > 4) by Cn_1. Then K n is isomorphic to either T (K6, A5, C5) (see Figure 1), or one of the graphs Kp- (i e Zpe_1, i < p-_1). Conversely, each of the above graphs is indeed a special generalized truncation of Kn (n > 4) by a cycle of length n — 1, where n = 6 or a prime power. Furthermore, for any distinct i,i' e Zp-_1 with i,i' < p-_1, Kp- = Kp- if and only if i' = ipj or —ip (mod pe — 1) for some 1 < j < e. Moreover, the following hold: (i) Aut(T(Ke,A5, C5)) = A5; (ii) Aut(K4) = S4; (iii) Aut(K7) = D42 x Z3; (iv) Aut(K?1) = PGL2(11); (v) Aut(K23) = PGL2(23); (vi) if Kp- is not isomorphic to one of the graphs: K4, K£, Kf1 and K^g, then Aut(Kp-) = AGL(1,pe). 328 Ars Math. Contemp. 19 (2020) 189-208 2 Preliminaries All groups considered in this paper are finite and all graphs are finite, connected, simple and undirected. For the group-theoretic and graph-theoretic terminology not defined here we refer the reader to [3, 12]. Let r = Cay(G, S) be a Cayley graph on a group G relative to a subset S of G. It is easy to prove that r is connected if and only if S is a generating subset of G. For any g G G, R(g) is the permutation of G defined by R(g) : x ^ xg for x g G. Set R(G) = {R(g) | g G G}. It is well-known that R(G) is a subgroup of Aut(r). For briefness, we shall identify R(G) with G in the following. In 1981, Godsil [7] proved that the normalizer of G in Aut(r) is G x Aut(G, S), where Aut(G, S) is the group of automorphisms of G fixing the set S set-wise. Clearly, Aut(G, S) is a subgroup of the stabilizer Aut(r)i of the identity 1 of G in Aut(r). We say that the Cayley graph Cay(G, S) is normal if G is normal in Aut(Cay(G, S)) (see [ ]). If r = Cay(G, S) is a normal Cayley graph on G, then we have Aut(G, S) = Aut(r)1, and if, in addition, r is also arc-transitive, then Aut(G, S) is transitive on S. From this we can easily obtain the following lemma. Lemma 2.1. There does not exist an arc-transitive normal Cayley graph of odd valency at least three on a cyclic group. A Cayley graph Cay(G, S) on a group G relative to a subset S of G is called a CI-graph of G, if for any Cayley graph Cay(G, T), whenever Cay(G, S) = Cay(G, T) we have T = Sa for some a G Aut(G). The following proposition is a criterion for a Cayley graph to be a CI-graph. Proposition 2.2 ([1, Lemma 3.1]). Let r be a Cayley graph on a finite group G. Then r is a CI-graph of G if and only if all regular subgroups of Aut(r) isomorphic to G are conjugate. Let r be a connected vertex-transitive graph, and let G < Aut(r) be vertex-transitive on r. For a G-invariant partition B of V(r), the quotient graph rB is defined as the graph with vertex set B such that, for any two different vertices B, C G B, B is adjacent to C if and only if there exist u G B and v G C which are adjacent in r. Let N be a normal subgroup of G. Then the set B of orbits of N in V(r) is a G-invariant partition of V(r). In this case, the symbol rB will be replaced by rN. In view of [11, Theorem 9], we have the following proposition. Proposition 2.3. Suppose that r is a connected trivalent graph with an arc-transitive group G of automorphisms. If N < G has more than two orbits in V(r), then N is semiregular on V(r), and rN is a trivalent symmetric graph with G/N as an arc-transitive group of automorphisms. 3 Proof of Theorem 1.4 3.1 Special generalized truncations of Kn by Cn-1 In this subsection, we shall prove the first part of Theorem 1.4 by determining all special generalized truncations of Kn (n > 4) by Cn-1. Throughout this subsection, we shall use the following assumptions and notations. X. Wang, F.-G. Yin and J.-X. Zhou: On generalized truncations of complete graphs 329 Assumption 3.1. (!) Let Kn be a complete graph of order n with n > 4, and let V (Kn) = {vi, v2,..., Vn}. (2) Let G < Aut(Kn) be an arc-transitive group of automorphisms. (3) Let v = vi, and let Ov be a union of orbits of the stabilizer Gv acting on {{x, y} | x = y, x,y G V(Kn) \ {v}}. Let T be the graph with vertex set {v2,v3,..., vn} and edge set Ov. (4) For each u G V(Kn), let Vu = {(u,w) | w G V(Kn) \ {u}}. (5) Let Kn = T(Kn, G, T) be the graph with the vertex set [jueV(Kri) Vu, and the adjacency relation in which a vertex (u, w) is adjacent to the vertex (w, u) and to all the vertices (u, w') for which there exists a g G G with the property ug = v and {w,w'}g G Ov. In view of [6, Theorem 5.1], we have the following proposition. Proposition 3.2. Use the notations in Assumption 3.!. Then Aut(Kn) has a vertex-transitive subgroup G such that P = {Vu | u G V(Kn)} is an imprimitivity block system for G. Furthermore, the following hold. (!) The quotient graph of Kn relative to P is isomorphic to Kn. (2) G = G. (3) G acts faithfully on P. For the two groups G, G in the above proposition, we shall follow [6] to say that G is the lift of G. The next lemma shows that if T = Cn-i then G is a 2-transitive permutation group on P and the point stabilizer GVu is either cyclic or dihedral. Lemma 3.3. Use the notations in Assumption 3.!. Let T = Cn-i and let G be the lift of G. Then for each u G V(Kn), the subgraph of Kn induced by Vu is a cycle of length n — 1, and the subgroup GVu of G fixing Vu set-wise acts faithfully and transitively on Vu. In particular, G acts faithfully and 2-transitively on P, and GVu = Zn-i, or Dn-i (if n is odd), or D2(n-i). Proof. By Assumption 3.1 (3) and (5), the subgraph of Kn induced by Vv is isomorphic to T. By Proposition 3.2, P = {Vu | u G V(Kn)} is an imprimitivity block system for G, and so for each u g V(Kn), the subgraph of Kn induced by Vu is a cycle of length n — 1. For any two vertices u, w of Kn, by Assumption 3.1 (5), {(u, w), (w, u)} is the unique edge of Kn connecting Vu and Vw. This implies that the subgroup K of GVu fixing Vu point-wise will fix every block in P. It then follows from Proposition 3.2 (3) that K =1, and so GVu acts faithfully on Vu. Since G is transitive on V(Kn), GVu is transitive on Vu. Since the subgraph of Kn induced by Vu is a cycle of length n — 1, one has GVu = Zn-i, or Dn-i (if n is odd), or D2(n-i). Again since {(u, w), (w, u)} is the unique edge of Kn connecting Vu and Vw, it follows that GVu also acts transitively on P \ {Vu}. This implies that G acts 2-transitively on P. By Proposition 3.2 (3), G acts faithfully on P. □ 330 Ars Math. Contemp. 19 (2020) 189-208 The above lemma enables us to determine the structure of G in the case when Y = Cn-1. Lemma 3.4. Use the notations in Assumption 3.1. Let Y = Cn-1 and let G be the lift of G. Then one of the following holds: (1) n = 6 and soc(G) = A5; (2) n = 4 and G ^ AGL(1, 22) or ArL(1, 22); (3) n = pe = 4 and G = AGL(1, pe), where p is a prime and e is a positive integer. Proof. By Lemma 3.3, G can be viewed as a 2-transitive permutation group on P with point stabilizer isomorphic to Zn-1, or Dn-1 (if n is odd), or D2(n-1). By [ , Propositon 5.2], soc(G) is either elementary abelian or non-abelian simple, and furthermore, if soc(G) is non-abelian simple, then by checking the list of the simple groups which can occur as socles of 2-transitive groups in [ , p. 8], we have soc(G) = A5. In order to complete the proof of this lemma, it remains to deal with the case when soc(G) is elementary abelian. In what follows, assume that soc(G) = Zp for some prime p and positive integer e. View soc(G) as an e-dimensional vector space over a field of order p, and let 0 denote the zero vector of soc(G). Recall that Go = Zpe_1, Dpe-1 (p odd), or D2(pe-1). By checking Hering's theorem on classification of 2-transitive affine permutation^groups [8] (see also [10, Appendix 1]), we have G < ArL(1,pe) with point-stabilizer G0 < TL(1,pe). As G = soc(G) x G0, to determine G, we only need to determine all possible subgroups of rL(1,pe) which are isomorphic to Zpe_1, Dpe_1 (p odd), or D2(pe_1), and transitive on soc(G) \ {0}. Note that TL(1,pe) can be constructed in the following way. Let GF(pe) be the Galois field of order pe, and view soc(G) as the additive group of GF(pe). It is well-known that the multiplicative group GF(pe) * of GF(pe) is cyclic, and let x be a generator of GF(pe) *. Then GL(1,pe) = (x). Let y be the Frobenius automorphism of GF(pe) such that y maps every g G GF(pe) to gp. Then we have rL(1,pe) = (x, y | xp -1 = ye = 1, y-1xy = xp). In the following, we shall first determine all possible cyclic subgroups of TL(1,pe) of order either pe -1 or (p odd) (Claim 1), and then this is used to determine all possible subgroups of rL(1,pe) which are isomorphic to Zpe_1, Dpe_1 (p odd), or D2(pe_1), and transitive on soc(G) \ {0}. Claim 1. Let T be a cyclic subgroup of TL(1,pe) of order p-_ with either r = 1 or r = 2 andp is odd. Then either T = (xr), or pe = 32, T = Zp°-i and T = (xy) or (x3y). 2 Proof of Claim 1. Let I = pe -1 or (p odd). Since T is acyclic subgroup of TL(1,pe) of order we may let T = (xjyk) with 0 < j < pe — 2 and 0 < k < e — 1. If k = 0, then T < (x) and so T = (xr) with either r =1 or r = 2 and p is odd. Assume now that 0 < k < e — 1. Then yk = 1. Since y_1xy = xp, one has yxpy_1 = x, and hence (yxy_1)p = x. Clearly, pe = 1 (mod pe — 1), so yxy_1 = xp X. Wang, F.-G. Yin and J.-X. Zhou: On generalized truncations of complete graphs 331 It follows that yk xj y k = xjp e , and so yk xj = xjp e yk .By this equality, we have for any positive integer m, mk (e — 1)_j (xjyk)m = xj(1+pfc(e—1)+P2k(e—1)k(e—1))ymfc = pk(=-i)-i ymk. (3.1) . pek(e—1) — 1 From Equation (3.1) it follows that (xjyk)e = xj pk(e—1)— 1 . Since pe — 1 | pfce(e-1) — 1, one has (xj yk )e(pk(e—1)-1) = xj(pek(e—1)-1) = 1. This implies that the order of xjyk divides e(pk(e-1) — 1), namely, ^ | e(pk(e-1) — 1). Since I = pe — 1 or (p odd), we have pe — 1 | 2e(pk(e_1) — 1). Suppose that e > 3. If (p, e) = (2,6), then I = pe — 1 = 63. However, it is easy to check that 63 \ 6(25k — 1) for any k < 5, contrary to I | e(pk(e-1) — 1). Thus, (p, e) = (2,6). Then by a result of Zsigmondy [14], there exists at least one prime q such that q divides pe — 1 but does not divide p4 — 1 for any positive integer t < e. Clearly, p = q, so p is an element of Z* = Zq-1 of order e. In particular, we have q > e. Since q | pe — 1 and pe — 1 | 2e(pk(e_1) — 1), we have q | pk(e-1) — 1, implying k(e — 1) > e. Since k < e — 1, we may let k(e — 1) = me +1 for some positive integers m and t < e, and sincepme(p4 — 1) = (pk(e-1) — 1) — (pme — 1), we have q | p4 — 1. However, this is impossible because it is assumed that q \ p4 — 1 for any t < e. Thus, e < 3. Since 0 < k < e — 1, one has e = 2 and k =1, and thenp2 — 1 | 4(p — 1). It follows that p +1 | 4 and hence p = 3. Then (xjy)2 = x4j has order at most 2 since (x) = Z8, and then xjy has order dividing 4. This implies that I = = 4 and T = (xy) or (x3y). This completes the proof of Claim 1. □ By now, we have shown that Claim 1 is true. Recall that G0 < TL(1,pe), G0 = Zpe_1, D pe_1 (p odd), or D2(pe_1) and G0 is transitive on soc(G) \ {0}. We shall finish the proof by considering the following three cases. Case 1. G0 = Zpe_1. In this case, by Claim 1, we must have G0 = (x) = GL(1, pe) and so G = AGL(1, pe). Case 2. G0 = Dpe_1 (p odd). In this case, by Claim 1, either x2 G G0, or pe = 9 and G0 contains xy or x3y. For the former, we have G0 = (x2,f), where f is an involution of TL(1,pe) such that 0 2 — (2 — 1 imnliAC that i=> io pi/pn anH Z- — _ /x2/ = x 2 and f ^ (x). Note that Go is transitive on soc(G) \ {0}. We may let f = xyk and 0 < k < e - 1. By Equation (3.1), f2 = (xyk)2 = 1 implies that e is even and k e(e-l) e(e-l) and furthermore, xp + 1 = 1. It follows that pe — 1 | p 2 + 1. However, since pe(pI + 1) = (pe 4. It follows that Kn is a Cayley graph on T (= AGL(1,pe)) and n = pe. For each u G V(Kn), by Lemma 3.3, the subgraph of Kn induced by Vu is a cycle of length n — 1, and the subgroup GVu of G fixing Vu set-wise acts faithfully and transitively on Vu. Furthermore, G acts faithfully and 2-transitively on P. For convenience, we may identify P with GF(pe), identify Vu with the zero element 0 of GF(pe) and identify T with AGL(1,pe). We shall use the notations for T = AGL(1,pe) as well as its elements and subgroups H and K introduced in the paragraph before Construction 1.2. Then TVu = K = Zp-_1. Take (u, w) G Vu, and assume that (u, w1) and (u, w2) are two vertices in Vu adjacent to (u, w). Since TTVu = K = Zp-_1 is transitive on Vu, there exists a unique axi 0 G TTVu such that (u, w)°xi,° = (u, w1) and (u, w)°x-i,° = (u, w2), and since the subgraph of Kn induced by Vu is a cycle of length n — 1, i is coprime to pe — 1 (n = pe). So we may let Kn = Cay(AGL(1,pe), {«x^.o, "x-,0, «xj}), where axjis an involution. Since Kn is connected, if p is odd, then we have axj = a p--i = a- 1z' and z' = 0, and if p = 2, then we have axj z/ = a1 z/ and z' = 0, and x 2 ,z' ' ' ' correspondingly, we obtain the two graphs Kp- (p > 2) and K2- (see Construction 1.2). □ From Figure 1 it is easy to see that T(K6, A5, C5) is a special generalized truncation of K6 by a cycle of length 5. The following lemma shows that each of the Cayley graphs Kp-(i G Zp-_1, i < p-_r1) is also indeed a special generalized truncation of Kp- by a cycle of length pe — 1. Lemma 3.6. Each of the graphs Kp- (i G Zp-_1, i < p-_1) (see Construction 1.2) is a special generalized truncation of Kp- by a cycle of length pe — 1. Proof. Recall that each Kp- (i G Z*-_1, i < ) is a trivalent Cayley graph on AGL(1,pe) defined as follows: Kp- = Cay(AGL(1,pe), {a_1,z', a^ ,o, ax-.,o}) (z' = 0,p > 2), K2- = Cay(AGL(1, 2e), {a1,z', ax.,o, ax-.,o}) (z' = 0). X. Wang, F.-G. Yin and J.-X. Zhou: On generalized truncations of complete graphs 333 (Keep in mind we use the notations for AGL(1,pe) as well as its elements and subgroups H and K introduced in the paragraph before Construction 1.2.) Note that AGL(1,pe ) = H x K, where H = {aM„ : z ^ z + z", Vz G GF(pe) | z" G GF(pe)}, K = {axj,0 : z ^ zxj, Vz G GF(pe) | j G Zp-_;t}. Moreover, K is maximal in AGL(1,pe) since AGL(1,pe) is 2-transitive on GF (pe). As i G Z*e_!, one has K = (axii0) and then the maximality of K implies that (a_1jZ', aXi,0) = AGL(1,pe) for p > 2 and (aM/,ov,0) = AGL(1,2e). Thus, every Kp-(i G Zpe_1, i < p-_) is connected. It is easy to see that Cay(K, {axij0, ax-i,0}) = Cp-_1 is a subgraph of Kp- (i G Zp-_1, i < p-_1 ). Since AGL(1,pe) acts on V(Kp- ) by right multiplication, the subgraph of Kp- induced by Kg for any g G AGL(1, pe ) is a cycle of length pe - 1. As AGL(1, pe ) acts 2-transitively on B = {Kg | g G AGL(1,pe)}, the quotient graph of Kp- relative to B is a complete graph Kp-. So we have Kp- = T(Kp-, AGL(1,pe), Tj), where Y is the subgraph with vertex set B - {K} and edge set {{KYg, KYO^og} | g G K} where Y = a_1jZ' for p> 2 and y = a1jZ for p = 2. □ 3.2 Automorphisms and isomorphisms In this subsection, we shall determine the automorphism groups and isomorphisms of special generalized truncations of Kn by Cn_ 1, and thus prove the second part of Theorem 1.4. By checking [6, Table 1], we have the following lemma. Lemma 3.7. Aut(T(Ke,^,^)) = A5. In the following two lemmas, we shall determine the automorphisms and isomorphisms of the graphs Kp- (i G Zp-_1, i < p-_1 ). We keep using the notations for AGL(1,pe) as well as its elements and subgroups H and K introduced in the paragraph before Construction 1.2. Lemma 3.8. Let r be one of the graphs Kp- (i G Zp-_1, i < p-_ ) (see Construction 1.2). Then Theorem 1.4 (ii)-(vi) hold. Proof. Recall that r is a connected trivalent Cayley graph on X = AGL(1,pe). Let A = Aut(r). For convenience of the statement, we view X as a regular subgroup of A. Suppose first that r is arc-transitive. Let N = p|geA Xg. If N =1, then by [ , Theorem 1.1], we have Aut(r) = PGL2(pe) withpe = 11 or 23. If pe = 11, then since i G Z10 and i < 5, we have i = 3 and hence r = K31. If pe = 23, then i = 3,5,7 or 9 as i G Z10 and i < 11, and by Magma [ ], Aut(K23) == PGL2(23) if and only if i = 7, and hence r = K23. If N > 1, then N < A, and in piirticular, N < X. Since soc(X) = Zp is the unique minimal normal subgroup of X = AGL(1,pe), one has soc(X) < N. Clearly, soc(X ) is a Sylow p-subgroup of N since N < X .So soc(X ) is characteristic in N and hence normal in A. Consider the quotient graph S of r relative to soc(X). Clearly, S has pe - 1 vertices. Since pe - 1 > 2, by Proposition 2.3, S would be a trivalent arc-transitive Cayley graph on X/ soc(X) = Zp-_1. Furthermore, by [2, Corollary 1.3], either S = K3,3, or S is a trivalent normal arc-transitive Cayley graph on X/ soc(X) = Zp-_1. However, the latter case cannot happen by Lemma 2.1. For the former, we have pe - 1 = 6 334 Ars Math. Contemp. 19 (2020) 189-208 and so p = 7 and e = 1. In this case, we have i = 1 and r = K7. By Magma [ ], we have Aut(K7) = D42 x Z3. Suppose now that r is not arc-transitive. If A > X, then the vertex-stabilizer Aa is a 2-group for any a e V(r). Then Aa fixes one and only one neighbor of a. Assume that the neighbor of a fixed by Aa is b. Then B = {{a, b}g | g e A} is a system of blocks of imprimitivity of A on V(r). It follows that r - B is a union of several cycles with equal lengths, and the set of vertex-sets of these cycles forms an A-invariant partition of V(r). Let C be the cycle of r containing the identity 1 of X. Since r is a Cayley graph on X, X acts on V(r) = X by right multiplication, and since V(C) is a block of imprimitivity of A acting on V(r), C is actually a subgroup of X. From the definition of r = Kp-, one may see that V(C) = K = {axi,o: z ^ zx®, Vz e GF(pe) | i e Zp-s1}, and the vertex set of every cycle of r - B is just a right coset of K. Let B = {Kg | g e X}. Then B is an A-invariant partition of r. Clearly, X acts 2-transitively and faithfully on B, so the quotient graph of r relative B is Kp-. Now it is easy to see that r = T(Kp-, A, Y®), where Y® is the subgraph with vertex set B - K and edge set {{KYg, K7axi,og} | g e AK} where Y = a_i,z/ for p > 2 and 7 = a^z' for p = 2. Clearly, Y® = Cp-s1. From Lemma 3.4 it follows that either pe =4 and A = ArL(1,4) = S4, or A = X = AGL(1,pe). □ Lemma 3.9. For any distinct i, i' e Z*es1 with i, i' < p-_1, Kp- = Kp- if and only if there exists 1 < j < e such that i' = ipj or — ip (mod pe — 1). Proof. If pe = 4 or 7, then we must have i =1, and so we have only one graph for each of these two cases. If pe = 11 or 23, then by Magma [ ], for any distinct i, i' e Z*-s1 with i, i' < p-_1, one may check that Kp- = Kp'- ifandonlyif i' = ipj or —ipj (mod pe — 1). Suppose that Kp- is not isomorphic to one of the graphs: K4, K1, Kf1 and K23. By Lemma 3.8, Aut(Kp-) = AGL(1,pe) and by Proposition 2.2, Kp- is a CI-graph. Recall that Kp- = Cay(AGL(1,pe), {a_1,z', «x-,o}) (p > 2), K2- = Cay(AGL(1, 2e), {«1,z', aai,o, aa-i,o}) (p = 2). Since Kp- is a CI-graph, for any distinct i, i' e Zp- s1 with i, i' < p-_1, Kp- = Kp- if and only if there exists 7 e Aut(AGL(1,pe)) such that {ax^,o, ax-^,o}7 = o, o} and either al 1 z, = as1,z/ for p > 2 or = a1,z' for p = 2. Note thas )Aut(A(_L'(1,pe)) = ArL(1,pe) = AGL(1,pe) x (n), where n is induced by the Frobenius automorphism of GF(pe) such that = aaP,bP for any aa,b e AGL(1,pe). Suppose first that i' = ipj or —ip^ (mod pe — 1) for some 1 < j < e. Then one may check that a±1 = a±1,z' and {ax»,o, ax-i,o}n a(z')-pjz',» = {axi' o,ax-i' o}. So Kp- = Kp-. Conversely, if Kp- = Kp-, then there exists 7 e Aut(AGL(1,pe)) such that {ax»,o, ax-i,o}7 = {axi' o, ax-i' o} and either al 1 z' = a_1z' for p > 2 or a^z' = a1,z' for p = 2. Since K = (axi,o), 7 normalizes K, and since NArL(1,p-)(K) = K x (n), one has 7 = axk,onj, for some k e Z*-s1 and 1 < j < e. Then axi,o = axi,o = axi,o = axipj ,o e {axi' ,o,ax-i' ,o}. It follows that i' = ipj or —ipj (mod pe — 1). □ X. Wang, F.-G. Yin and J.-X. Zhou: On generalized truncations of complete graphs 335 3.3 Proof of Theorem 1.4 From Lemmas 3.5 and 3.6 we can obtain the proof of the first part of Theorem 1.4, and from Lemmas 3.8 and 3.9, we obtain the proof of the second part of Theorem 1.4. ORCID iDs Xue Wang © https://orcid.org/0000-0001-5131-6353 Fu-Gang Yin © https://orcid.org/0000-0001-8328-0690 Jin-Xin Zhou D https://orcid.org/0000-0002-8353-896X References [1] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977), 329-336, doi:10.1007/bf01895854. [2] Y.-G. Baik, Y. Feng, H.-S. Sim and M. Xu, On the normality of Cayley graphs of abelian groups, Algebra Colloq. 5 (1998), 297-304, doi:10.1023/a:1006016130005. [3] N. Biggs, Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2nd edition, 1993. [4] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235-265, doi:10.1006/jsco.1996.0125. [5] P. J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), 1-22, doi:10.1112/blms/13.1.1. [6] E. Eiben, R. Jajcay and P. Sparl, Symmetry properties of generalized graph truncations, J. Comb. Theory Ser. B 137 (2019), 291-315, doi:10.1016/j.jctb.2019.01.002. [7] C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981), 243-256, doi:10.1007/bf02579330. [8] C. Hering, Transitive linear groups and linear groups which contain irreducible subgroups of prime order, II, J. Algebra 93 (1985), 151-164, doi:10.1016/0021-8693(85)90179-6. [9] J. J. Li and Z. P. Lu, Cubic s-arc transitive Cayley graphs, Discrete Math. 309 (2009), 60146025, doi:10.1016/j.disc.2009.05.002. [10] M. W. Liebeck, The affine permutation groups of rank three, Proc. London Math. Soc. 54 (1987), 477-516, doi:10.1112/plms/s3-54.3.477. [11] P. Lorimer, Vertex-transitive graphs: symmetric graphs of prime valency, J. Graph Theory 8 (1984), 55-68, doi:10.1002/jgt.3190080107. [12] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964. [13] M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309-319, doi:10.1016/s0012-365x(97)00152-0. [14] K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math. Phys. 3 (1892), 265-284, doi: 10.1007/bf01692444.