ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P2.02 / 175–200 https://doi.org/10.26493/1855-3974.2373.c02 (Also available at http://amc-journal.eu) Trivalent dihedrants and bi-dihedrants* Mi-Mi Zhang School of Mathematical Sciences, Hebei Normal University, Shijiazhuang, 050024, China Jin-Xin Zhou † Department of Mathematics, Beijing Jiaotong University, Beijing, 100044, China Received 3 July 2020, accepted 22 February 2021, published online 21 October 2021 Abstract A Cayley (resp. bi-Cayley) graph on a dihedral group is called a dihedrant (resp. bi- dihedrant). In 2000, a classification of trivalent arc-transitive dihedrants was given by Marušič and Pisanski, and several years later, trivalent non-arc-transitive dihedrants of or- der 4p or 8p (p a prime) were classified by Feng et al. As a generalization of these results, our first result presents a classification of trivalent non-arc-transitive dihedrants. Using this, a complete classification of trivalent vertex-transitive non-Cayley bi-dihedrants is given, thus completing the study of trivalent bi-dihedrants initiated in our previous paper [Dis- crete Math. 340 (2017) 1757–1772]. As a by-product, we generalize a theorem in [The Electronic Journal of Combinatorics 19 (2012) #P53]. Keywords: Cayley graph, non-Cayley, bi-Cayley, dihedral group, dihedrant, bi-dihedrant. Math. Subj. Class. (2020): 05C25, 20B25 1 Introduction In this paper we describe an investigation of trivalent Cayley graphs on dihedral groups as well as vertex-transitive trivalent bi-Cayley graphs over dihedral groups. To be brief, we shall say that a Cayley (resp. bi-Cayley) graph on a dihedral group a dihedrant (resp. bi-dihedrant). Cayley graphs are usually defined in the following way. Given a finite group G and an inverse closed subset S ⊆ G\{1}, the Cayley graph Cay(G,S) on G with respect to S is a graph with vertex set G and edge set {{g, sg} | g ∈ G, s ∈ S}. For any g ∈ G, R(g) is the *This work was supported by the National Natural Science Foundation of China (11671030, 12101181) and the Natural Science Foundation of Hebei Province (A2019205180) †Corresponding author. E-mail addresses: mmzhang@hebtu.edu.cn (Mi-Mi Zhang), jxzhou@bjtu.edu.cn (Jin-Xin Zhou) cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 176 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 permutation of G defined by R(g) : x 7→ xg for x ∈ G. Set R(G) := {R(g) | g ∈ G}. It is well-known that R(G) is a subgroup of Aut (Cay(G,S)). We say that the Cayley graph Cay(G,S) is normal if R(G) is normal in Aut (Cay(G,S)) (see [19]). In 2000, Marušič and Pisanski [13] initiated the study of automorphisms of dihedrants, and they gave a classification of trivalent arc-transitive dihedrants. Following this work, highly symmetrical dihedrants have been extensively studied, and one of the remarkable achievements is the complete classification of 2-arc-transitive dihedrants (see [7, 12]). In contrast, however, relatively little is known about the automorphisms of non-arc-transitive dihedrants. In [1], the authors claimed that every trivalent non-arc-transitive dihedrant is normal. However, this is not true. There exist non-arc-transitive and non-normal dihe- drants. Actually, in [22, 26], the automorphism groups of trivalent dihedrants of order 4p and 8p are determined for each prime p, and the result reveals that every non-arc-transitive trivalent dihedrant of order 4p or 8p is either a normal Cayley graph, or isomorphic to the so-called cross ladder graph. For an integer m ≥ 2, the cross ladder graph, denoted by CL4m, is a trivalent graph of order 4m with vertex set V0∪V1∪ . . . V2m−2∪V2m−1, where Vi = {x0i , x1i }, and edge set {{xr2i, xr2i+1}, {xr2i+1, xs2i+2} | i ∈ Zm, r, s ∈ Z2} (see Fig. 1 for CL4m). It is worth mentioning that the cross ladder graph plays an important role in the · · ·     S S S S S     S S S S S     S S S S S· · · • • • • • • • • • • • • • • • • x02m−1 x 0 0 x 0 1 x 0 2 x 0 3 x 0 2m−4 x 0 2m−3 x 0 2m−2 x12m−1 x 1 0 x 1 1 x 1 2 x 1 3 x 1 2m−4 x 1 2m−3 x 1 2m−2 Figure 1: The cross ladder graph CL4m study of automorphisms of trivalent graphs (see, for example, [5, 21, 26]). Motivated by the above mentioned facts, we shall focus on trivalent non-arc-transitive dihedrants. Our first theorem generalizes the results in [22, 26] to all trivalent dihedrants. Theorem 1.1. Let Σ = Cay(H,S) be a connected trivalent Cayley graph, where H = ⟨a, b | an = b2 = 1, bab = a−1⟩(n ≥ 3). If Σ is non-arc-transitive and non-normal, then n is even and Σ ∼= CL4·n2 and S α = {b, ba, ban2 } for some α ∈ Aut (H). Recall that for an integer m ≥ 2, the cross ladder graph CL4m has vertex set V0 ∪ V1 ∪ . . . V2m−2 ∪ V2m−1, where Vi = {x0i , x1i }. The multi-cross ladder graph, denoted by MCL4m,2, is the graph obtained from CL4m by blowing up each vertex xri of CL4m into two vertices xr,0i and x r,1 i . The edge set is {{x r,s 2i , x r,t 2i+1}, {x r,s 2i+1, x s,r 2i+2} | i ∈ Zm, r, s, t ∈ Z2} (see Fig. 2 for MCL20,2). Note that the multi-cross ladder graph MCL4m,2 is just the graph given in [23, Def- inition 7]. From [6, Proposition 3.3] we know that every MCL4m,2 is vertex-transitive. However, not all multi-cross ladder graphs are Cayley graphs. Actually, in [23, Theo- rem 9], it is proved that MCL4p,2 is a vertex-transitive non-Cayley graph for each prime p > 7. Our second theorem generalizes this result to all multi-cross ladder graphs. Theorem 1.2. The multi-cross ladder graph MCL4m,2 is a Cayley graph if and only if either m is even, or m is odd and 3 | m. Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 177 t t t t t t t t t t t @ @ @@ t t @ @ @@ t t @ @ @@ t t @ @ @@ t t @ @ @@ t t t @ @ @@ t t @ @ @@ t t @ @ @@ t t @ @ @@ t t t @ @ @@ t t @ @ @@ t t @ @ @@ t t @ @ @@ t t @ @ @@ t x0,00 x 0,0 1 x 0,0 2 x 0,0 3 x 0,0 4 x 0,0 5 x 0,0 6 x 0,0 7 x 0,0 8 x 0,0 9 x1,10 x 1,1 1 x 1,1 2 x 1,1 3 x 1,1 4 x 1,1 5 x 1,1 6 x 1,1 7 x 1,1 8 x 1,1 9 x1,00 x 1,0 1 x 1,0 2 x 1,0 3 x 1,0 4 x 1,0 5 x 1,0 6 x 1,0 7 x 1,0 8 x 1,0 9 x0,10 x 0,1 1 x 0,1 2 x 0,1 3 x 0,1 4 x 0,1 5 x 0,1 6 x 0,1 7 x 0,1 8 x 0,1 9 Figure 2: The multi-cross ladder graph MCL20,2 Both of the above two theorems are crucial in attacking the problem of classification of trivalent vertex-transitive non-Cayley bi-dihedrants. Before proceeding, we give some background to this topic, and set some notation. Let R,L and S be subsets of a group H such that R = R−1, L = L−1 and R ∪ L does not contain the identity element of H . The bi-Cayley graph BiCay(H,R,L, S) over H relative to R,L, S is a graph having vertex set the union of the right part H0 = {h0 | h ∈ H} and the left part H1 = {h1 | h ∈ H}, and edge set the union of the right edges {{h0, g0} | gh−1 ∈ R}, the left edges {{h1, g1} | gh−1 ∈ L} and the spokes {{h0, g1} | gh−1 ∈ S}. If |R| = |L| = s, then BiCay(H, R, L, S) is said to be an s-type bi-Cayley graph. In [20] we initiated a program to investigate the automorphism groups of the trivalent vertex-transitive bi-dihedrants. This was partially motivated by the following facts. As one of the most important finite graphs, the Petersen graph is a bi-circulant, but it is not a Cayley graph. Note that a bi-circulant is a bi-Cayley graph over a cyclic group. The Petersen graph is the initial member of a family of graphs P (n, t), known now as the generalized Petersen graphs (see [17]), which can be also constructed as bi-circulants. Let n ≥ 3, 1 ≤ t < n/2 and set H = ⟨a⟩ ∼= Zn. The generalized Petersen graph P (n, t) is isomorphic to the bi-circulant BiCay(H, {a, a−1}, {at, a−t}, {1}). The complete classification of vertex-transitive generalized Petersen graphs has been worked out in [8, 14]. Latter, this was generalized by Marušič et al. in [13, 15] where all trivalent vertex- transitive bi-circulants were classified, and more recently, all trivalent vertex-transitive bi- Cayley graphs over abelian groups were classified in [24]. The characterization of trivalent vertex-transitive bi-dihedrants is the next natural step. Another motivation for us to consider trivalent vertex-transitive bi-dihedrants comes from the excellent work in a highly cited article [16], where the authors give a census of trivalent vertex-transitive graphs of order up to 1280. This is very important in the study of trivalent vertex-transitive graphs. Actually, by checking this census of graphs of order up to 1000, we find out that there are 981 non-Cayley graphs, and among these graphs, 233 graphs are non-Cayley bi-dihedrants. This may suggest bi-dihedrants form an important class of trivalent vertex-transitive non-Cayley graphs. In [20], we gave a classification of trivalent arc-transitive bi-dihedrants, and we also proved that every trivalent vertex-transitive 0- or 1-type bi-dihedrant is a Cayley graph, and gave a classification of trivalent vertex-transitive non-Cayley bi-dihedrants of order 4n with 178 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 n odd. The goal of this paper is to complete the classification of trivalent vertex-transitive non-Cayley bi-dihedrants. Before stating the main result, we need the following concepts. For a bi-Cayley graph Γ = BiCay(H, R, L, S) over a group H , we can assume that the identity 1 of H is in S (see Proposition 2.3 (2)). The triple (R,L, S) of three subsets R,L, S of a group H is called bi-Cayley triple if R = R−1, L = L−1, and 1 ∈ S. Two bi-Cayley triples (R,L, S) and (R′, L′, S′) of a group H are said to be equivalent, denoted by (R,L, S) ≡ (R′, L′, S′), if either (R′, L′, S′) = (R,L, S)α or (R′, L′, S′) = (L,R, S−1)α for some automorphism α of H . The bi-Cayley graphs corresponding to two equivalent bi-Cayley triples of the same group are isomorphic (see Proposition 2.3 (3)-(4)). Theorem 1.3. Let Γ = BiCay(R,L, S) be a trivalent vertex-transitive bi-dihedrant where H = ⟨a, b | an = b2 = 1, bab = a−1⟩ is a dihedral group. Then either Γ is a Cayley graph or one of the following occurs: (1) (R,L, S) ≡ ({b, ba}, {a, a−1}, {1}), where n = 5. (2) (R,L, S) ≡ ({b, baℓ+1}, {ba, baℓ2+ℓ+1}, {1}), where n ≥ 5, ℓ3 + ℓ2 + ℓ + 1 ≡ 0 (mod n), ℓ2 ̸≡ 1 (mod n). (3) (R,L, S) ≡ ({ba−ℓ, baℓ}, {a, a−1}, {1}), where n = 2m and ℓ2 ≡ −1 (mod m). Furthermore, Γ is also a bi-Cayley graph over an abelian group Zn × Z2. (4) (R,L, S) ≡ ({b, ba}, {b, ba2m}, {1}), where n = 2(2m + 1), m ̸≡ 1 (mod 3), and the corresponding graph is isomorphic the multi-cross ladder graph MCL4m,2. (5) (R,L, S) ≡ ({b, ba}, {ba24ℓ, ba12ℓ−1}, {1}), where n = 48ℓ and ℓ ≥ 1. Moreover, all of the graphs arising from (1)-(4) are vertex-transitive non-Cayley. 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, 18]. 2.1 Definitions and notations For a positive integer, let Zn be the cyclic group of order n and Z∗n be the multiplicative group of Zn consisting of numbers coprime to n. For two groups M and N , N ⋊ M denotes a semidirect product of N by M . For a subgroup H of a group G, denote CG(H) the centralizer of H in G and by NG(H) the normalizer of H of G. Let G be a permutation group on a set Ω and α ∈ Ω. Denote by Gα the stabilizer of α in G. We say that G is semiregular on Ω if Gα = 1 for every α ∈ Ω and regular if G is transitive and semiregular. For a finite, simple and undirected graph Γ, we use V (Γ), E(Γ), A(Γ), Aut (Γ) to denote its vertex set, edge set, arc set and full automorphism group, respectively. For any subset B of V (Γ), the subgraph of Γ induced by B will be denoted by Γ[B]. For any v ∈ V (Γ) and a positive integer i no more than the diameter of Γ, denote by Γi(v) be the set of vertices at distance i from v. Clearly, Γ1(v) is just the neighborhood of v. We shall often abuse the notation by using Γ(v) to replace Γ1(v). A graph Γ is said to be vertex-transitive, and arc-transitive (or symmetric) if Aut (Γ) acts transitively on V (Γ) and A(Γ), respectively. Let Γ be a connected vertex-transitive Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 179 graph, and let G ≤ Aut (Γ) be vertex-transitive on Γ. For a G-invariant partition B of V (Γ), the quotient graph ΓB is defined as the graph with vertex set B such that, for any two different vertices B,C ∈ B, B is adjacent to C if and only if there exist u ∈ B and v ∈ C which are adjacent in Γ. Let N be a normal subgroup of G. Then the set B of orbits of N in V (Γ) is a G-invariant partition of V (Γ). In this case, the symbol ΓB will be replaced by ΓN . The original graph Γ is said to be a N -cover of ΓN if Γ and ΓN have the same valency. 2.2 Cayley graphs Let Γ = Cay(G,S) be a Cayley graph on G with respect to S. Then Γ is vertex-transitive due to R(G) ≤ Aut (Γ). In general, we have the following proposition. Proposition 2.1 ([2, Lemma 16.3]). A vertex-transitive graph Γ is isomorphic to a Cayley graph on a group G if and only if its automorphism group has a subgroup isomorphic to G, acting regularly on the vertex set of Γ. In 1981, Godsil [9] proved that the normalizer of R(G) in Aut (Cay(G,S)) is R(G)⋊ Aut (G,S), where Aut (G,S) is the group of automorphisms of G fixing the set S set- wise. This result has been successfully used in characterizing various families of Cayley graphs Cay(G,S) such that R(G) = Aut (Cay(G,S)) (see, for example, [9, 10]). Recall that a Cayley graph Cay(G,S) is said to be normal if R(G) is normal in Aut (Cay(G,S)) (see [19]). Proposition 2.2 ([19, Proposition 1.5]). The Cayley graph Γ = Cay(G,S) is normal if and only if A1 = Aut (G,S), where A1 is the stabilizer of the identity 1 of G in Aut (Γ). 2.3 Basic properties of bi-Cayley graphs In this subsection, we let Γ be a connected bi-Cayley graph BiCay(H,R,L, S) over a group H . It is easy to prove some basic properties of such a Γ, as in [24, Lemma 3.1]. Proposition 2.3. The following hold. (1) H is generated by R ∪ L ∪ S. (2) Up to graph isomorphism, S can be chosen to contain the identity of H . (3) For any automorphism α of H , BiCay(H, R, L, S) ∼= BiCay(H, Rα, Lα, Sα). (4) BiCay(H, R, L, S) ∼= BiCay(H, L, R, S−1). Next, we collect several results about the automorphisms of bi-Cayley graph Γ = BiCay(H, R, L, S). For each g ∈ H , define a permutation as follows: R(g) : hi 7→ (hg)i, ∀i ∈ Z2, h ∈ H. (2.1) Set R(H) = {R(g) | g ∈ H}. Then R(H) is a semiregular subgroup of Aut (Γ) with H0 and H1 as its two orbits. For an automorphism α of H and x, y, g ∈ H , define two permutations of V (Γ) = H0 ∪H1 as follows: δα,x,y : h0 7→ (xhα)1, h1 7→ (yhα)0, ∀h ∈ H, σα,g : h0 7→ (hα)0, h1 7→ (ghα)1, ∀h ∈ H. (2.2) 180 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 Set I = {δα,x,y | α ∈ Aut (H) s.t. Rα = x−1Lx, Lα = y−1Ry, Sα = y−1S−1x}, F = {σα,g | α ∈ Aut (H) s.t. Rα = R, Lα = g−1Lg, Sα = g−1S}. (2.3) Proposition 2.4 ([25, Theorem 1.1]). Let Γ = BiCay(H,R,L, S) be a connected bi- Cayley graph over the group H . Then NAut (Γ)(R(H)) = R(H) ⋊ F if I = ∅ and NAut (Γ)(R(H)) = R(H)⟨F, δα,x,y⟩ if I ̸= ∅ and δα,x,y ∈ I . Furthermore, for any δα,x,y ∈ I , we have the following: (1) ⟨R(H), δα,x,y⟩ acts transitively on V (Γ); (2) if α has order 2 and x = y = 1, then Γ is isomorphic to the Cayley graph Cay(H̄, R∪ αS), where H̄ = H ⋊ ⟨α⟩. 3 Cross ladder graphs The goal of this section is to prove Theorem 1.1. Proof of Theorem 1.1. Suppose that Σ = Cay(H,S) is a connected trivalent Cayley graph which is neither normal nor arc-transitive, where H = ⟨a, b | an = b2 = 1, bab = a−1⟩(n ≥ 3). Then S is a generating subset of H and |S| = 3. So S must contain an involution of H outside ⟨a⟩. As Aut (H) is transitive on the coset b⟨a⟩, we may assume that S = {b, x, y} for x, y ∈ H \ ⟨b⟩. Suppose first that x is not an involution. Then we must have y = x−1. Since S generates H , one has ⟨a⟩ = ⟨x⟩, and so bxb = x−1. Then there exists an automorphism of H sending b, x to b, a respectively. So we may assume that S = {b, a, a−1}. Now it is easy to check that Σ is isomorphic to the generalized Petersen graph P (n, 1). Since Σ is not arc-transitive, by [8, 14], we have |Aut (Σ)| = 2|H|, and so Σ would be a normal Cayley graph of H , a contradiction. Therefore, both x and y must be involutions. Suppose that x ∈ ⟨a⟩. Then n is even and x = an/2. Again since S generates H , one has y = baj , where 1 ≤ j ≤ n − 1 and either (j, n) = 1 or (j, n) = 2 and n2 is odd. Note that the subgroup of Aut (H) fixing b is transitive on the set of generators of ⟨a⟩ and that ⟨an/2⟩ is the center of H . There exists α ∈ Aut (H) such that Sα = {b, ba, an2 } or {b, ba2, an2 }. Without loss of generality, we may assume that S = {b, ba, an2 } or {b, ba2, an2 }. If S = {b, ba2, an2 }, we shall prove that Σ ∼= P (n, 1). Note that the generalized Petersen graph P (n, 1) has vertex set {ui, vi | i ∈ Zn} and edge set {{ui, ui+1}, {vi, vi+1}, {ui, vi} | i ∈ Zn}. Define a map from V (Σ) to V (P (n, 1)) as follows: φ : a2i 7→ u2i, a2i+ n 2 7→ v2i, ba2i 7→ u2i−1, ba2i+ n 2 7→ v2i−1, where 0 ≤ i ≤ n2 − 1. It is easy to see that φ is an isomorphism form Σ to P (n, 1). Since Σ is not arc-transitive, by [8, 14], we have |Aut (Σ)| = 2|H|, and so Σ would be a normal Cayley graph of H , a contradiction. If S = {b, ba, an2 }, then Σ has a connected subgraph Σ1 = Cay(H, {b, ba}) which is a cycle of length 2n, and Σ is just the graph obtained from Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 181 Σ1 by adding a 1-factor such that each vertex g of Σ1 is adjacent to its antipodal vertex a n 2 g. Then R(H) ⋊ Z2 ∼= Aut (Σ1) ≤ Aut (Σ), and then since Σ is assumed to be not arc-transitive, Aut (Σ) will fix the 1-factor {{g, an2 g} | g ∈ H} setwise. This implies that Aut (Σ) ≤ Aut (Σ1) and so Aut (Σ) = Aut (Σ1). Consequently, we have Σ is a normal Cayley graph of H , a contradiction. Similarly, we have y /∈ ⟨a⟩. Then we may assume that x = bai and y = baj for some 1 ≤ i, j ≤ n − 1 and i ̸= j. Then S = {b, bai, baj} ⊆ b⟨a⟩. This implies that Σ is a bipartite graph with ⟨a⟩ and b⟨a⟩ as its two partition sets. Since Σ is not arc-transitive, Aut (Σ)1 is intransitive on the neighbourhood S of 1, and since Σ is not a normal Cayley graph of H , there exists a unique element, say s ∈ S, such that Aut (Σ)1 = Aut (Σ)s. Considering the fact that Aut (H) is transitive on b⟨a⟩, without loss of generality, we may assume that Aut (Σ)1 = Aut (Σ)b and Aut (Σ)1 swaps bai and baj . Then for any h ∈ H , we have Aut (Σ)h = (Aut (Σ)1)R(h) = (Aut (Σ)b)R(h) = Aut (Σ)bh. Direct computation shows that Σ2(1) = {a−i, a−j , ai, ai−j , aj , aj−i}, Σ3(1) = {ba−i, baj−i, ba−j , bai−j , ba2i, baj+i, ba2i−j , ba2j , ba2j−i}. Let Aut (Σ)∗1 be the kernel of Aut (Σ)1 acting on S. Take an α ∈ Aut (Σ)∗1. Then α fixes every element in S. As Aut (Σ)h = Aut (Σ)bh for any h ∈ H , α will fix b(bai) = ai and b(baj) = aj . Note that Σ(bai) \ {1, ai} = {ai−j} and Σ(baj) \ {1, aj} = {aj−i}. Then α also fixes ai−j and aj−i, and then α also fixes bai−j and baj−i. If |Σ2(1)| = 6, then it is easy to check that a−i is the unique common neighbor of b and baj−i. So α also fixes a−i. Now one can see that α fixes every vertex in Σ2(1). If |Σ2(1)| < 6 and either |Σ1(b) ∩ Σ1(bai)| > 1 or |Σ1(b) ∩ Σ1(baj)| > 1, then α also fixes every vertex in Σ2(1). In the above two cases, by the connectedness and vertex-transitivity of Σ, α would fix all vertices of Σ, implying that α = 1. Hence, Aut (Σ)∗1 = 1 and Aut (Σ)1 ∼= Z2. This forces that Σ is a normal Cayley graph of H , a contradiction. Thus, we have |Σ2(1)| < 6 and |Σ1(b) ∩ Σ1(bai)| = |Σ1(b) ∩ Σ1(baj)| = 1. This implies that Σ1(bai) ∩ Σ1(baj) = {1, ai−j} = {1, aj−i}, and so ai−j = aj−i. It follows that ai−j is an involution, and hence n is even and ai−j = an/2. So S = {b, bai, bai+n/2}. As S generates H , one has ⟨ai, an/2⟩ = ⟨a⟩. So either (i, n) = 1 or (i, n) = 2 and n2 is odd. Note that the subgroup of Aut (H) fixing b is transitive on the set of generators of ⟨a⟩ and that ⟨an/2⟩ is the center of H . There exists α ∈ Aut (H) such that Sα = {b, ba, ba1+n2 } or {b, ba2, ba2+n2 }. Let βϵ be the automorphism of H induced by the map a 7→ a−1, b 7→ baϵ, where ϵ ∈ Z2. Then {b, ba, ba1+n2 }β1 = {b, ba, ban2 }, and {b, ba2, ba2+n2 }β2 = {b, ba2, ban2 }. If n2 is odd, then the map η : a 7→ a 2+n2 , b 7→ ban2 induces an automorphism of H , and {b, ba, ban2 }η = {b, ba2, ban2 }. So there always exists γ ∈ Aut (H) such that Sγ = {b, ba, ban2 }, completing the proof of the first part of our theorem. Finally, we shall prove Σ ∼= CL4·n2 . Without loss of generality, assume that S = {b, ba, ban2 }. Recall that V (CL4·n2 ) = {x r i | i ∈ Z2n, r ∈ Z2} and E(CL4·n2 ) = 182 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 {{xri , xri+1}, {xr2i, x r+1 2i+1}, | i ∈ Z2n, r ∈ Z2}. Let ϕ be a map from V (Σ) to V (CL4·n2 ) as following: ϕ : ai 7→ x02i, ai+ n 2 7→ x12i, baj 7→ x02j−1, baj+ n 2 7→ x12j−1, where 0 ≤ i ≤ n2 − 1 and 1 ≤ j ≤ n 2 . It is easy to check that ϕ is an isomorphism from Σ and X(CL4·n2 ), as desired. 4 Multi-cross ladder graphs The goal of this section is to prove Theorem 1.2. We first show that each MCL4m,2 is a bi-Cayley graph. Lemma 4.1. The multi-cross ladder graph MCL4m,2 is isomorphic to the bi-Cayley graph BiCay(H, {c, ca}, {ca, ca2b}, {1}), where H = ⟨a, b, c | am = b2 = c2 = 1, ab = a, ac = a−1, bc = b⟩. Proof. For convenience, let Γ be the bi-Cayley graph given in our lemma, and let X = MCL4m,2. Let ϕ be a map from V (X) to V (Γ) defined by the following rule: ϕ : x1,12t 7→ (at)0, x 1,1 2t+1 7→ (cat+1)0, x 1,0 2t 7→ (cat+1)1, x 1,0 2t+1 7→ (at)1, x0,12t 7→ (cat+1b)1, x 0,1 2t+1 7→ (atb)1, x 0,0 2t 7→ (atb)0, x 0,0 2t+1 7→ (cat+1b)0, where t ∈ Zm. It is easy to see that ϕ is an adjacency preserving isomorphism from X to Γ. Remark 1 Let m be odd, let e = ab and f = ca. Then the group given in Lemma 4.1 has the following presentation: H = ⟨e, f | e2m = f2 = 1, ef = e−1⟩. Clearly, in this case, H is a dihedral group. Furthermore, the corresponding bi-Cayley graph given in Lemma 4.1 will be BiCay(H, {f, fe}, {f, fem−1}, {1}). Proof of Theorem 1.2. By Lemma 4.1, we may let Γ = MCL4m,2 be just the bi-Cayley graph BiCay(H,R,L, S), where H = ⟨a, b, c | am = b2 = c2 = 1, ab = a, ac = a−1, bc = b⟩, R = {c, ca}, L = {ca, ca2b}, S = {1}. We first prove the sufficiency. Assume first that m is even. Then the map a 7→ ab, b 7→ b, c 7→ cb induces an automorphism, say α of H of order 2. Furthermore, Rα = {c, ca}α = caLca, Lα = {ca, ca2b}α = caRca and Sα = {1}α = ca{1}ca = S−1. By Proposition 2.4, δα,ca,ca ∈ Aut (Γ) and R(H)⋊⟨δα,ca,ca⟩ acts regularly on V (Γ). Consequently, by Propo- sition 2.1, Γ is a Cayley graph. Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 183 Assume now that m is odd and 3 | m. In this case, we shall use the bi-Cayley presen- tation for Γ as in Remark 5.1, that is, Γ = BiCay(H, {f, fe}, {f, fem−1}, {1}), where H = ⟨e, f | e2m = f2 = 1, ef = e−1⟩. Let β be a permutation of V (Γ) defined as following: β : (f ie3t+1)i ↔ (f iem+3t+1)i, (f i+1e3t+1)i ↔ (f iem+3t+1)i+1, (f i+1e3t+2)i ↔ (f i+1em+3t+2)i, (f ie3t+2)i ↔ (f i+1em+3t+2)i+1, (e3t)i ↔ (fe3t)i+1, (em+3t)i ↔ (fem+3t)i+1, where t ∈ Zm 3 and i ∈ Z2. It is easy to check that β is an automorphism of Γ of order 2. Furthermore, R(e),R(f) and β satisfy the following relations: R(e)2m = R(f)2 = β2 = 1, R(f)−1R(e)R(f) = R(e)−1, R(f)−1βR(f) = β, R(e)6β = βR(e)6, R(e)2β = βR(e)4βR(e)−2. Let G = ⟨R(e2),R(f), β⟩ and P = ⟨R(e2), β⟩. Then R(f) /∈ P and G = P ⟨R(f)⟩. Since R(e)6β = βR(e)6, we have R(e6) ∈ Z(P ). Since R(e)2β = βR(e)4βR(e)−2, it follows that (R(e)2β)3 = R(e)2β[βR(e)4βR(e)−2]R(e)2β = R(e6). Let N = ⟨R(e6)⟩. Clearly, N is a normal subgroup of G. Furthermore, P/N = ⟨R(e2)N, βN | R(e2)3N = β2N = (R(e2)β)3N = N⟩ ∼= A4. Therefore, |P | = 4m and |G| ≤ 8m. Let ∆00 = {x0 | x ∈ ⟨e2, f⟩}, ∆10 = {(ex)0 | x ∈ ⟨e2, f⟩}, ∆01 = {x1 | x ∈ ⟨e2, f⟩}, ∆11 = {(ex)1 | x ∈ ⟨e2, f⟩}. Then ∆ij’s (i, j ∈ Z2) are four orbits of ⟨R(e2),R(f)⟩. Moreover, 1 βR(f) 0 = 11 ∈ ∆01, e β 0 = (e m+1)0 ∈ ∆00, eβ1 = (fem+1)0 ∈ ∆00. This implies that G is transitive on V (Γ). Hence, |G| = 8m and so G is regular on V (Γ), and by Proposition 2.1, Γ is a Cayley graph. To prove the necessity, it suffices to prove that if m is odd and 3 ∤ m, then Γ is a non- Cayley graph. In this case, we shall use the original definition of Γ = MCL4m,2. Suppose that m is odd and 3 ∤ m. We already know from [6, Proposition 3.3] that Γ is vertex- transitive. Let A = Aut (Γ). For m = 5 or 7, using Magma [4], Γ is a non-Cayley graph. In what follows, we assume that m ≥ 11. For each j ∈ Zm, C0j = (x 0,0 2j , x 0,0 2j+1, x 0,1 2j , x 0,1 2j+1) and C 1 j = (x 1,1 2j , x 1,1 2j+1, x 1,0 2j , x 1,0 2j+1) are two 4-cycles. Set F = {Cij | i ∈ Z2, j ∈ Zm}. From the construction of Γ = MCL4m,2, it is easy to see that in Γ = MCL4m,2 passing each vertex there is exactly one 4- cycle, which belongs to F . Clearly, any two distinct 4-cycles in F are vertex-disjoint. This implies that ∆ = {V (Cij) | i ∈ Z2, j ∈ Zm} is an A-invariant partition of V (Γ). Consider 184 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 the quotient graph Γ∆, and let T be the kernel of A acting on ∆. Then Γ∆ ∼= Cm[2K1], the lexicographic product of a cycle of length m and an empty graph of order 2. Hence A/T ≤ Aut (Cm[2K1]) ∼= Zm2 ⋊ D2m. Note that between any two adjacent vertices of Γ∆ there is exactly one edge of Γ = MCL4m,2. Then T fixes each vertex of Γ and hence T = 1. So we may view A as a subgroup of Aut (Γ∆) ∼= Aut (Cm[2K1]) ∼= Zm2 ⋊D2m. For convenience, we will simply use the Cij’s to represent the vertices of Γ∆. Then Γ∆ has vertex set {C0j ,C1j | j ∈ Zm} and edge set {{C0j ,C0j+1}, {C1j ,C1j+1}, {C0j ,C1j+1}, {C1j ,C0j+1} | j ∈ Zm}. Let B = {{C0j ,C1j} | j ∈ Zm}. Then B is an Aut (Γ∆)-invariant partition of V (Γ∆). Let K be the kernel of Aut (Γ∆) acting on B. Then K = ⟨k0⟩ × ⟨k2⟩ × · · · × ⟨km−1⟩, where we use ki to denote the transposition (C0j C 1 j ) for j ∈ Zm. Clearly, K is the maximal normal 2-subgroup of Aut (Γ∆). Suppose to the contrary that Γ = MCL4m,2 is a Cayley graph. By Proposition 2.1, A has a subgroup, say G acting regularly on V (Γ). Then G has order 8m, and G/(G ∩K) ∼= GK/K ≤ Aut (Γ∆)/K ≲ D2m. Since m odd, it follows that |G ∩K| = 4 or 8, and so G ∩K ∼= Z22 or Z32. If G ∩ K ∼= Z22, then |GK/K| = 2m and GK/K = Aut (Γ∆)/K ∼= D2m. So GK = Aut (Γ∆) ∼= Zm2 ⋊ D2m. Let M be a Hall 2′-subgroup of G. Then M ∼= Zm and M is also a Hall 2′-subgroup of Aut (Γ∆). Clearly, Aut (Γ∆) is solvable, so all Hall 2′-subgroups of Aut (Γ∆) are conjugate. Without loss of generality, we may let M = ⟨α⟩, where α is the following permutation on V (Γ∆): α = (C00 C 0 1 . . .C 0 m−1)(C 1 0 C 1 1 . . .C 1 m−1). Then K ⋊ ⟨α⟩ acts transitively on V (Γ∆). Clearly, CK(α) is contained in the center of K ⋊ ⟨α⟩. So CK(α) is semiregular on V (Γ∆). This implies that CK(α) = ⟨k0k1 . . . km−1⟩ ∼= Z2. On the other hand, let L = (G ∩ K)M . Clearly, G ∩ K ⊴ G, so L is a subgroup of G of order 4m. For any odd prime factor p of m, let P be a Sylow p-subgroup of M . Then P is also a Sylow p-subgroup of L, and since M is cyclic, one has M ≤ NL(P ). By Sylow theorem, we have |L : NL(P )| = kp + 1 | 4 for some integer k. Since 3 ∤ m, one has L = NL(P ). It follows that M ⊴ L and so L = M × (G ∩ K). This implies that G ∩K ≤ CK(M) = CK(α) ∼= Z2, a contradiction. If G ∩ K ∼= Z32, then |GK/K| = m. Furthermore, GK/K ∼= Zm and GK/K acts on B regularly. Since G is transitive on V (Γ), there exists g ∈ G such that (x1,10 )g = x1,11 , where x 1,1 0 , x 1,1 1 ∈ C 1 0. As V (Γ∆) = {Cij | i ∈ Z2, j ∈ Zm}, g fixes the 4-cycle C10 = (x 1,1 0 , x 1,1 1 , x 1,0 0 , x 1,0 1 ). Since B = {{C 0 j ,C 1 j} | j ∈ Zm} is also A-invariant, g fixes {C00,C10} setwise. Since GK/K acts on B regularly, g fixes {C0j ,C1j} setwise for every j ∈ Zm. Observe that {x1,10 , x 1,1 2m−1} and {x 1,1 1 , x 1,1 2 } are the unique edges of Γ between C10 and C 1 m−1, C 1 0 and C 1 2, respectively. This implies that g will map C 1 m−1 to C 1 2, contradicting that g fixes {C0j ,C1j} setwise for every j ∈ Zm. Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 185 5 A family of trivalent VNC bi-dihedrants The goal of this section is to prove the following lemma which gives a new family of trivalent vertex-transitive non-Cayley bi-dihedrants. To be brief, a vertex-transitive non- Cayley graph is sometimes simply called a VNC graph. Lemma 5.1. Let H = ⟨a, b | an = b2 = 1, ab = a−1⟩ be a dihedral group, where n = 48ℓ and ℓ ≥ 1. Then Γ = BiCay(H, {b, ba}, {ba24ℓ, ba12ℓ−1}, {1}) is a VNC dihedrant. Proof. We first define a permutation on V (Γ) as follows: g : (a3r)0 7→ (a3r)0, (a3r)1 7→ (ba3r)0, (a3r+1)0 7→ (ba3r+1)1, (a3r+1)1 7→ (a24ℓ+3r+1)1, (a3r+2)i 7→ (ba12ℓ+3r+2)i+1, (ba3r)0 7→ (a3r)1, (ba3r)1 7→ (ba24ℓ+3r)1, (ba3r+1)0 7→ (ba3r+1)0, (ba3r+1)1 7→ (a3r+1)0, (ba3r+2)i 7→ (a−12ℓ+3r+2)i+1, where r ∈ Z16ℓ, i ∈ Z2. It is easy to check that g is an involution, and furthermore, for any t ∈ Z16ℓ, we have Γ((a3r)0) g = {(a3r)1, (ba3r)0, (ba3r+1)0} = Γ((a3r)0), Γ((a3r)1) g = {(ba3r)1, (a3r)0, (a3r−1)0} = Γ((ba3r)0), Γ((ba3r)1) g = {(ba24ℓ+3r)0, (a3r)1, (a12ℓ+3r+1)1} = Γ((ba24ℓ+3r)1), Γ((a3r+1)0) g = {(ba3r+1)0, (a24ℓ+3r+1)1, (a36ℓ+3r+2)1} = Γ((ba3r+1)1), Γ((a3r+1)1) g = {(a24ℓ+3r+1)0, (ba3r+1)1, (ba36ℓ+3r)1} = Γ((a24ℓ+3r+1)1), Γ((ba3r+1)0) g = {(ba3r+1)1, (a3r+1)0, (a3r)0} = Γ((ba3r+1)0), Γ((a3r+2)0) g = {(ba12ℓ+3r+2)0, (a36ℓ+3r+2)1, (a3r+3)1} = Γ((ba12ℓ+3r+2)1), Γ((a3r+2)1) g = {(ba12ℓ+3r+2)1, (a12ℓ+3r+2)0, (a12ℓ+3r+1)0} = Γ((ba12ℓ+3r+2)0). This implies that g is an automorphism of Γ. Observing that g maps 11 to b0, it follows that ⟨R(H), g⟩ is transitive on V (Γ), and so Γ is a vertex-transitive graph. Below, we shall first prove the following claim. Claim. Aut (Γ)10 = ⟨g⟩. Let A = Aut (Γ). It is easy to see that g fixes 10, and so g ∈ A10 . To prove the Claim, it suffices to prove that |A10 | = 2. Note that the neighborhood Γ(10) of 10 in Γ is = {11, b0, (ba)0}. By a direct com- putation, we find that in Γ there is a unique 8-cycle passing through 10, 11 and b0, that is, C0 = (10, 11, (ba24ℓ)1, (ba24ℓ)0, (a24ℓ)0, (a24ℓ)1, b1, b0, 10). Furthermore, in Γ there is no 8-cycle passing through 10 and (ba)0. So A10 fixes (ba)0. If A10 also fixes 11 and b0, then A10 will fix every neighbor of 10, and the connected- ness and vertex-transitivity of Γ give that A10 = 1, a contradiction. Therefore, A10 swaps 11 and b0, and (ba)0 is the unique neighbor of 10 such that A10 = A(ba)0 . It follows that {10, (ba)0} is a block of imprimitivity of A acting on V (Γ). Since Γ is vertex-transitive, every v ∈ V (Γ) has a unique neighbor, say u such that Au = Av . Then the set B = {{u, v} ∈ E(Γ) | Au = Av} forms an A-invariant partition of V (Γ). Clearly, {10, (ba)0} ∈ B. Similarly, since C0 is also the unique 8-cycle of Γ passing through 10, 11 and b0, A11 swaps 10 and b0, and 186 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 (ba12ℓ−1)1 is the unique neighbor of 11 such that A11 = A(ba12ℓ−1)1 . So {11, (ba12ℓ−1)1} ∈ B. Set B0 = {{10, (ba)0}R(h) | h ∈ H} and B1 = {{11, (ba12ℓ−1)1}R(h) | h ∈ H}. Clearly, B = B0 ∪ B1. Now we consider the quotient graph ΓB of Γ relative to B. It is easy to see that ⟨R(a)⟩ acts semiregularly on B with B0 and B1 as its two orbits. So ΓB is isomorphic to a bi- Cayley graph over ⟨a⟩. Set B0 = {10, (ba)0} and B1 = {11, (ba12ℓ−1)1}. Then one may see that the neighbors of B0 in ΓB are: B R(a) 0 , B R(a−1) 0 , B1, B R(a−12ℓ+2) 1 , and the neighbors of B1 in ΓB are: B R(a12ℓ+1) 1 , B R(a−12ℓ−1) 1 , B0, B R(a12ℓ−2) 0 . So ΓB ∼= Γ′ = BiCay(⟨a⟩, {a, a−1}, {a12ℓ+1, a−12ℓ−1}, {1, a−12ℓ+2}). Observe that there is one and only one edge of Γ between B0 and any one of its neighbors in ΓB. Clearly, A acts transitively on V (ΓB), so there is one and only one edge of Γ between every two adjacent blocks of B. It follows that A acts faithfully on V (ΓB), and hence we may view A as a subgroup of Aut (ΓB). Recall that g ∈ A10 = A(ba)0 . Moreover, g swaps the two neighbors 11 and b0 of 10. Clearly, 11 ∈ B1 and b0 ∈ BR(a −1) 0 , so g swaps the two blocks B1 and B R(a−1) 0 . Similarly, g swaps the two neighbors (ba)1 and a0 of (ba)0. Clearly, (ba)1 ∈ BR(a −12ℓ+2) 1 and a0 ∈ B R(a) 0 , so g swaps the two blocks B R(a−12ℓ+2) 1 and B R(a) 0 . Note that R(ab) swaps the two vertices in B0. So ⟨g,R(ab)⟩ acts transitively on the neighborhood of B0 in ΓB. This implies that A acts transitively on the arcs of ΓB, and so Γ′ is a tetravalent arc-transitive bi-circulant. In [11], a characterization of tetravalent edge- transitive bi-circulants is given. It is easy to see that our graph Γ′ belongs to Class 1(c) of [11, Theorem 1.1]. By checking [11, Theorem 4.1], we see that the stabilizer Aut (Γ′)u of u ∈ V (Γ′) has order 4. This implies that |A| = 4|V (ΓB)| = 8n. Consequently, |A10 | = 2 and so our claim holds. Now we are ready to finish the proof. Suppose to the contrary that Γ is a Cayley graph. By Proposition 2.1, A contains a subgroup, say J acting regularly on V (Γ). By Claim, J has index 2 in A, and since g ∈ A10 , one has A = J ⋊ ⟨g⟩. It is easy to check that R(a),R(b) and g satisfy the following relations: (gR(b))4 = R(a24ℓ), gR(a3) = R(a3)g, gR(ba) = R(ba)g, g = R(a)(gR(b))2R(a12ℓ−1). Suppose that R(H) ≰ J . Then A = JR(H). Since |J |/|R(H)| = 2, it follows that |R(H) : J ∩ R(H)| = 2. Thus, J ∩ R(H) = ⟨R(a)⟩ or ⟨R(a2),R(b)⟩. If R(H) ∩ J = ⟨R(a)⟩, then we have R(b) /∈ J , R(a) ∈ J , and hence A = J∪JR(b) = J∪Jg, implying that JR(b) = Jg. It follows that gR(b) ∈ J , and then g = R(a)(gR(b))2R(a12ℓ−1) ∈ J due to R(a) ∈ J , a contradiction. If R(H)∩J = ⟨R(a2),R(b)⟩, then R(a) /∈ J , and again we have A = J∪JR(a) = J∪Jg, implying that JR(a) = Jg. So, R(a)g, gR(a−1) ∈ J . Then g = R(a)gR(b)gR(b)R(a12ℓ−1) = (R(a)g)R(b)(gR(a−1))R(ba12ℓ−2) ∈ J, a contradiction. Suppose that R(H) ≤ J . Then |J : R(H)| = 2 and R(H) ⊴ J . Since J is regular on V (Γ), by Proposition 2.4, there exists a δα,x,y ∈ J such that 1 δα,x,y 0 = 11, where α ∈ Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 187 Aut (H) and x, y ∈ H . By the definition of δα,x,y , we have 11 = 1 δα,x,y 0 = (x · 1α)1 = x1, implying that x = 1. Furthermore, we have the following relations: Rα = x−1Lx,Lα = y−1Ry, Sα = y−1S−1x, where R = {b, ba}, L = {ba24ℓ, ba12ℓ−1}, S = {1}. In particular, the last equality implies that x = y due to S = {1}. So we have x = y = 1. From the proof of Claim we know that B0 = {10, (ba)0} and B1 = {11, (ba12ℓ−1)1} are two blocks of imprimitivity of A acting on V (Γ). So we have ((ba)0)δα,1,1 = (ba12ℓ−1)1. It follows that (ba)α = ba12ℓ−1, and then from Rα = L we obtain that bα = ba24ℓ. Consequently, we have aα = a36ℓ−1. One the other hand, we have {b, ba} = R = Lα = {b, ba24ℓ+1}. This forces that ba = ba24ℓ+1, which is clearly impossible. 6 Two families of trivalent Cayley bi-dihedrants In this section, we shall prove two lemmas which will be used the proof of Theorem 1.3. Lemma 6.1. Let H = ⟨a, b | a12m = b2 = 1, ab = a−1⟩ be a dihedral group with m odd. Then for each i ∈ Z12m, Γ = BiCay(H, {b, bai}, {ba6m, ba3m−i}, {1}) is a Cayley graph whenever ⟨ai, a3m⟩ = ⟨a⟩. Proof. Let g be a permutation of V (Γ) defined as follows: g : (a6km+3ri)j 7→ (ba6(k+1)m+3ri)j+1, (ba6km+3ri)j 7→ (a6km+3ri)j+1, (a3km+(3r+1)i)0 7→ (a3(k+1)m+(3r+1)i)0, (ba3km+(3r+1)i)0 7→ (a3(k+1)m+(3r+1)i)1, (a3km+(3r+1)i)1 7→ (ba3(k+1)m+(3r+1)i)0, (ba3km+(3r+1)i)1 7→ (ba3(k−1)m+(3r+1)i)1, (a3km+(3r+2)i)0 7→ (ba3(k+1)m+(3r+2)i)1, (ba3km+(3r+2)i)0 7→ (ba3(k+1)m+(3r+2)i)0, (a3km+(3r+2)i)1 7→ (a3(k−1)m+(3r+2)i)1, (ba3km+(3r+2)i)1 7→ (a3(k+1)m+(3r+2)i)0, where r ∈ Zm, k ∈ Z4 and j ∈ Z2. It is easy to check that g ∈ Aut (Γ). Furthermore, one may check that g and R(a2) satisfy the following relations: R(a12m) = g4 = 1, g2 = R(a6m), R(a6)g = gR(a6), R(b−1)gR(b) = gR(a6m), R(a2)g = gR(a4)gR(a−2). By the last equality, we have (R(a2)g)3 = [gR(a4)gR(a−2))]R(a2)gR(a2)g = gR(a4)g2R(a2)g. It then follows from the second and third equalities that gR(a4)g2R(a2)g = gR(a6+6m)g = g2R(a6+6m) = R(a6). Therefore, (R(a2)g)3 = R(a6). Let G = ⟨R(a2),R(b), g⟩ and T = ⟨R(a6)⟩. Then T ⊴G and G/T = ⟨R(a2)T,R(b)T, gT ⟩ = ⟨R(a2)T, gT | R(a2)3T = g2T = (R(a2)g)3T = T ⟩⋊ ⟨R(b)T ⟩ ∼= A4 ⋊ Z2. 188 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 So |G| = 48m. Let Ω00 = {t0 | t ∈ ⟨a2, b⟩}, Ω01 = {t1 | t ∈ ⟨a2, b⟩}, Ω10 = {(at)0 | t ∈ ⟨a2, b⟩}, Ω11 = {(at)1 | t ∈ ⟨a2, b⟩}. Then Ωij’s (0 ≤ i, j ≤ 1) are orbits of T and V (Γ) = ⋃ 0≤i,j≤1 Ωij . Since 1 g 0 = (ba 6m)1 ∈ Ω01, a g 0 = (a 3m+1)0 ∈ Ω00 and ag1 = (ba3m+1)1 ∈ Ω01, it follows that G is transitive, and so regular on V (Γ). By Proposition 2.1, Γ is a Cayley graph on G, as required. Lemma 6.2. Let H = ⟨a, b | a12m = b2 = 1, ab = a−1⟩ be a dihedral group with m even and 4 ∤ m. Then the following two bi-Cayley graphs: Γ1 = BiCay(H, {b, ba}, {ba6m, ba3m−1}, {1}), Γ2 = BiCay(H, {b, ba}, {ba6m, ba9m−1}, {1}) are both Cayley graphs. Proof. Let V = H0 ∪H1. Then V (Γ1) = V (Γ2) = V . We first define two permutations on V as follows: g1 : (a 4r)i 7→ (ba6m+4r)i+1, (ba4r)i 7→ (a4r)i+1, (a4r+1)i 7→ (ba9m+4r+1)i+1, (ba4r+1)i 7→ (a3m+4r+1)i+1, (a4r+2)i 7→ (ba4r+2)i+1, (ba4r+2)i 7→ (a6m+4r+2)i+1, (a4r+3)i 7→ (ba3m+4r+3)i+1, (ba4r+3)i 7→ (a9m+4r+3)i+1, g2 : (a 4r)i 7→ (ba6m+4r)i+1, (ba4r)i 7→ (a4r)i+1, (a4r+1)i 7→ (ba3m+4r+1)i+1, (ba4r+1)i 7→ (a9m+4r+1)i+1, (a4r+2)i 7→ (ba4r+2)i+1, (ba4r+2)i 7→ (a6m+4r+2)i+1, (a4r+3)i 7→ (ba9m+4r+3)i+1, (ba4r+3)i 7→ (a3m+4r+3)i+1, where r ∈ Z3m and i ∈ Z2. It is easy to check that gj ∈ Aut (Γj) for j = 1 or 2. Furthermore, R(a2),R(b) and gj (j = 1 or 2) satisfy the following relations: R(a12m) = R(b2) = g4j = 1,R(b)R(a2)R(b) = R(a−2), g2j = R(a6m),R(b)gjR(b) = g −1 j , g−11 R(a)g1 = R(a3m+1), g −1 2 R(a)g2 = R(a9m+1). For j = 1 or 2, let Gj = ⟨R(a),R(b), gj⟩. From the above relations it is east to see that Gj = (⟨R(a)⟩⟨gj⟩)⋊ ⟨R(b)⟩ has order at most 48m. Observe that 1gj0 = (ba 6m)1 ∈ H1 for j = 1 or 2. It follows that Gj is transitive on V (Γj), and so Gj acts regularly on V (Γj). By Proposition 2.1, each Γj is a Cayley graph. 7 Vertex-transitive trivalent bi-dihedrants In this section, we shall give a complete classification of trivalent vertex-transitive non- Cayley bi-dihedrants. For convenience of the statement, throughout this section, we shall make the following assumption. Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 189 Assumption I. • H: the dihedral group D2n = ⟨a, b | an = b2 = 1, bab = a−1⟩(n ≥ 3), • Γ = BiCay(H, R, L, {1}): a connected trivalent 2-type vertex-transitive bi-Cayley graph over the group H (in this case, |R| = |L| = 2), • G: a minimum group of automorphisms of Γ subject to that R(H) ≤ G and G is transitive on the vertices but intransitive on the arcs of Γ. The following lemma given in [20] shows that the group G must be solvable. Lemma 7.1 ([20, Lemma 6.2]). G = R(H)P is solvable, where P is a Sylow 2-subgroup of G. 7.1 H0 and H1 are blocks of imprimitivity of G The case where H0 and H1 are blocks of imprimitivity of G has been considered in [20], and the main result is the following proposition. Proposition 7.2 ([20, Theorem 1.3]). If H0 and H1 are blocks of imprimitivity of G on V (Γ), then either Γ is Cayley or one of the following occurs: (1) (R,L, S) ≡ ({b, baℓ+1}, {ba, baℓ2+ℓ+1}, {1}), where n ≥ 5, ℓ3 + ℓ2 + ℓ + 1 ≡ 0 (mod n), ℓ2 ̸≡ 1 (mod n); (2) (R,L, S) ≡ ({ba−ℓ, baℓ}, {a, a−1}, {1}), where n = 2k and ℓ2 ≡ −1 (mod k). Furthermore, Γ is also a bi-Cayley graph over an abelian group Zn × Z2. Furthermore, all of the graphs arising from (1)-(2) are vertex-transitive non-Cayley. In particular, it is proved in [20] that if n is odd and Γ is not a Cayley graph, then H0 and H1 are blocks of imprimitivity of G on V (Γ). Consequently, we can get a classification of trivalent vertex-transitive non-Cayley bi-Cayley graphs over a dihedral group D2n with n odd. Proposition 7.3 ([20, Proposition 6.4]). If n is odd, then either Γ is a Cayley graph, or H0 and H1 are blocks of imprimitivity of G on V (Γ). 7.2 H0 and H1 are not blocks of imprimitivity of G In this subsection, we shall consider the case where H0 and H1 are not blocks of imprimi- tivity of G on V (Γ). We begin by citing a lemma from [20]. Lemma 7.4 ([20, Lemma 6.3]). Suppose that H0 and H1 are not blocks of imprimitivity of G on V (Γ). Let N be a normal subgroup of G, and let K be the kernel of G acting on V (ΓN ). Let ∆ be an orbit of N . If N fixes H0 setwise, then one of the following holds: (1) Γ[∆] has valency 1, |V (ΓN )| ≥ 3 and Γ is a Cayley graph; (2) Γ[∆] has valency 0, ΓN has valency 3, and K = N is semiregular. The following lemma deals with the case where CoreG(R(H)) = 1, and in this case we shall see that Γ is just the cross ladder graph. 190 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 Lemma 7.5. Suppose that H0 and H1 are not blocks of imprimitivity of G on V (Γ). If CoreG(R(H)) = ⋂ g∈G R(H) = 1, then Γ is isomorphic to the cross ladder graph CL4n with n odd, and furthermore, for any minimal normal subgroup N of G, we have the following: (1) N is a 2-group which is non-regular on V (Γ); (2) N does not fix H0 setwise; (3) every orbit of N consists of two non-adjacent vertices. Proof. Let N be a minimal normal subgroup of G. By Lemma 7.1, G is solvable. It follows that N is an elementary abelian r-subgroup for some prime divisor r of |G|. Clearly, N ≰ R(H) due to CoreG(R(H)) = 1. Then |NR(H)|/|R(H)| | |G|/|R(H)|. From Lemma 7.1 it follows that |G|/|R(H)| is a power of 2, and hence N is a 2-group. Suppose that N is regular on V (Γ). Then NR(H) is transitive on V (Γ) and R(H) is also a 2-group. Therefore, NR(H) is not transitive on the arcs of Γ. The minimality of G gives that G = NR(H). Since n is even, R(an2 ) is in the center of R(H). Set Q = N⟨R(an2 )⟩. Then Q⊴G and then 1 ̸= N ∩Z(Q)⊴G. Since N is a minimal normal subgroup of G, one has N ≤ Z(Q), and hence Q is abelian. It follows that ⟨R(an2 )⟩⊴G, contrary to the assumption that CoreG(R(H)) = 1. Thus, N is not regular on V (Γ). (1) is proved. For (2), by way of contradiction, suppose that N fixes H0 setwise. Consider the quo- tient graph ΓN of Γ relative to N , and let K be the kernel of G acting on V (ΓN ). Take ∆ to be an orbit of N on V (Γ). Then either (1) or (2) of Lemma 7.4 happens. For the former, Γ[∆] has valency 1 and |V (ΓN )| ≥ 3. Then ΓN is a cycle. Moreover, any two neighbors of u ∈ ∆ are in different orbits of N . It follows that the stabilizer Nv of v in N fixes every neighbor of u. The connectedness of Γ implies that Nv = 1. Thus, K = N is semiregular and ΓN is a cycle of length ℓ = 2|R(H)|/|N |. So G/N ≤ Aut (ΓN ) ∼= D2ℓ. If G/N < Aut (ΓN ), then |G : N | = ℓ and so |G| = 2|R(H)|. This implies that R(H) ⊴ G, contrary to the assumption that CoreG(R(H)) = 1. If G/N = Aut (ΓN ), then |G : R(H)| = 4. Since N ̸≤ R(H) and since N fixes H0 setwise, one has |G : R(H)N | = 2. It follows that R(H)N ⊴G. Clearly, H0 and H1 are just two orbits of R(H)N , and they are also two blocks of imprimitivity of G on V (Γ), a contradiction. For the latter, Γ[∆] has valency 0, ΓN has valency 3 and N = K is semiregular. Let H̄i be the set of orbits of N contained in Hi with i = 1, 2. Then ΓN [H̄0] and ΓN [H̄1] are of valency 2 and the edges between H̄0 and H̄1 form a perfect matching. Without loss of generality, we may assume that 10 ∈ ∆. Since R(H) acts on H0 by right multiplication, we have the subgroup of R(H) fixing ∆ setwise is just R(H)∆ = {R(h) | h0 ∈ ∆}. If R(H)∆ ≤ ⟨R(a)⟩, then R(H)∆ ⊴ R(H), and the transitivity of R(H) on H0 implies that R(H)∆ will fix all orbits of N contained in H0. Since the edges between H̄0 and H̄1 are independent, R(H)∆ fixes all orbits of N . It follows that R(H)∆ ≤ N , namely, R(H)N/N acts regularly on H̄0. Then |R(H)/(R(H)∩N)| = |R(H)N/N | = |H0/N |, and so |N | = |R(H) ∩ N |, forcing N ≤ R(H), a contradiction. Thus, R(H)∆ ≰ ⟨R(a)⟩, and so ⟨R(a)⟩R(H)∆ = R(H). This implies that ⟨R(a), N⟩/N is transitive and so regular on H̄0. Similarly, ⟨R(a), N⟩/N is also regular on H̄1. Thus, ΓN is a trivalent 2-type bi-Cayley graph over ⟨R(a), N⟩/N . By [24, Lemma 5.3], H̄0 and H̄0 are blocks of imprimitivity of G/N , and so H0 and H1 are blocks of imprimitivity of G, a contradiction. Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 191 So far, we have completed the proof of (2). Then N does not fix H0 setwise, and then NR(H) is transitive on V (Γ). The minimality of G gives that G = NR(H). Let P and P1 be Sylow 2-subgroups of G and R(H), respectively, such that P1 ≤ P . Then N ≤ P and P = NP1. If n is even, then by a similar argument to the second paragraph, a contradiction occurs. Thus, n is odd. As H ∼= D2n, P1 ∼= Z2 and P1 is non-normal in R(H). So N∩R(H) = 1. Clearly, |V (Γ)| = 4n. If N is semiregular on V (Γ), then N ∼= Z2 or Z2 × Z2, and then |G| = |R(H)||N | = 2|R(H)| or 4|R(H)|. Since CoreG(R(H)) = 1, we must have |G : R(H)| = 4 and G ≲ Sym(4). Since n is odd, one has n = 3 and H ∼= Sym(3). So G ∼= Sym(4) and hence G10 ∼= Z2. Then all involutions of G(∼= Sym(4)) not contained in N are conjugate. Take 1 ̸= g ∈ G10 . Then g is an involution which is not contained in N because N is semiregular on V (Γ). Since R(H) ∩ N = 1, every involution in R(H) would be conjugate to g. This is clearly impossible because R(H) is semiregular on V (Γ). Thus, N is not semiregular on V (Γ). (3) is proved. Since n is odd, we have |V (ΓN )| > 2. Since N is not semiregular on V (Γ), ΓN has valency 2 and Γ[∆] has valency 0. This implies that the subgraph induced by any two adjacent two orbits of N is either a union of several cycles or a perfect matching. Thus, ΓN has even order. As Γ has order 4n with n odd, every orbit of N has length 2. It is easy to see that Γ is isomorphic to the cross ladder graph CL4n. The following is the main result of this section. Theorem 7.6. Suppose that H0 and H1 are not blocks of imprimitivity of G on V (Γ). Then Γ = BiCay(H,R,L, S) is vertex-transitive non-Cayley if and only if one of the followings occurs: (1) (R,L, S) ≡ ({b, ba}, {b, ba2m}, {1}), where n = 2(2m + 1), m ̸≡ 1 (mod 3), and the corresponding graph is isomorphic the multi-cross ladder graph MCL4m,2; (2) (R,L, S) ≡ ({b, ba}, {ba24ℓ, ba12ℓ−1}, {1}), where n = 48ℓ and ℓ ≥ 1. Proof. The sufficiency can be obtained from Theorem 1.2 and Lemma 5.1. We shall prove the necessity in the following subsection by a series of lemmas. 7.3 Proof of the necessity of Theorem 7.6 The purpose of this subsection is to prove the necessity of Theorem 7.6. Throughout this subsection, we shall always assume that H0 and H1 are not blocks of imprimitivity of G on V (Γ) and that Γ = BiCay(H,R,L, S) is vertex-transitive non-Cayley. In this subsection, we shall always use the following notation. Assumption II. Let N = CoreG(R(H)). Our first lemma gives some properties of the group N . Lemma 7.7. 1 < N < ⟨R(a)⟩, |⟨R(a)⟩ : N | = n/|N | is odd and the quotient graph ΓN of Γ relative to N is isomorphic to the cross ladder graph CL4n/|N |. Proof. If N = 1, then from Lemma 7.5 it follows that Γ ∼= CL4n which is a Cayley graph by Theorem 1.1, a contradiction. Thus, N > 1. Since H0 and H1 are not blocks of imprimitivity of G on V (Γ), one has N < R(H). 192 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 Consider the quotient graph ΓN . Clearly, N fixes H0 setwise. Recall that H0 and H1 are not blocks of imprimitivity of G on V (Γ) and that Γ is non-Cayley. Applying Lemma 7.4, we see that ΓN is a trivalent 2-type bi-Cayley graph over R(H)/N . This implies that |R(H) : N | > 2, and since H is a dihedral group, one has N < ⟨R(a)⟩. Again, by Lemma 7.4, R(H)/N acts semiregularly on V (ΓN ) with two orbits, H̄0 and H̄1, where H̄i is the set of orbits of N contained in Hi with i = 1, 0. Furthermore, N is just the kernel of G acting on V (ΓN ) and N acts semiregularly on V (Γ). Then G/N is also a minimal vertex-transitive automorphism group of ΓN containing R(H)/N . If H̄0 and H̄1 are blocks of imprimitivity of G/N on V (ΓN ), then H0 and H1 will be blocks of imprimitivity of G on V (Γ), which is impossible by our assumption. Thus, H̄0 and H̄1 are not blocks of imprimitivity of G/N on V (ΓN ). Since N = CoreG(R(H)), CoreG/N (R(H)/N) is trivial. Then from Lemma 7.5 it follows that ΓN ∼= CL 4n|N| , where n |N | is odd. Next, we introduce another notation which will be used in the proof. Assumption III. Take M/N to be a minimal normal subgroup of G/N . We shall first consider some basic properties of the quotient graph ΓM of Γ relative to M . Lemma 7.8. The quotient graph ΓM of Γ relative to M is a cycle of length n/|N |. Fur- thermore, every orbit of M on V (Γ) is a union of an orbit of N on H0 and an orbit of N on H1, and these two orbits of N are non-adjacent. Proof. Applying Lemma 7.5 to ΓN and G/N , we obtain the following facts: (a) M/N is an elementary abelian 2-group which is not regular on V (ΓN ), (b) M/N does not fix H̄0 setwise, (c) every orbit of M/N on V (ΓN ) consists of two non-adjacent vertices of ΓN . From (b) and (c) it follows that every orbit of M on V (Γ) is just a union of an orbit of N on H0 and an orbit of N on H1, and these two orbits are non-adjacent. Since every orbit of N on V (Γ) is an independent subset of V (Γ), each orbit of M on V (Γ) is also an independent subset. Recall that ΓN ∼= CL4m where m = n|N | is odd. The quotient graph of ΓN relative to M/N is just a cycle of length m, and so the quotient graph ΓM of Γ relative to M is also a cycle of length m. By Lemma 7.8, each orbit of M on V (Γ) is an independent subset. It follows that the subgraph induced by any two adjacent orbits of M is either a perfect matching or a union of several cycles. For convenience of the statement, the following notations will be used in the remainder of the proof: Assumption IV. (1) Let ∆ and ∆′ be two adjacent orbits of M on V (Γ) such that Γ[∆ ∪∆′] is a union of several cycles. (2) Let ∆ = ∆0 ∪∆1 and ∆′ = ∆′0 ∪∆′1, where ∆0,∆′0 ⊆ H0 and ∆1,∆′1 ⊆ H1 are four orbits of N on V (Γ). Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 193 (3) 10 ∈ ∆0. Since Γ[∆] and Γ[∆′] are both null graphs and since Γ[∆ ∪ ∆′] is a union of several cycles, we have the following easy observation. Lemma 7.9. Γ[∆i ∪∆′j ] is a perfect matching for any 0 ≤ i, j ≤ 1. The following lemma tells us the possibility of R (Recall that we assume that Γ = BiCay(H,R,L, {1})). Lemma 7.10. Up to graph isomorphism, we may assume that R = {b, bai} with i ∈ Zn \ {0} and that b0 ∈ ∆′0. Furthermore, we have ∆0 = {h0 | R(h) ∈ N},∆′0 = {(bh)0 | R(h) ∈ N}, ∆′1 = {h1 | R(h) ∈ N},∆1 = {(bh)1 | R(h) ∈ N}, and 11 is adjacent to (bal)1 ∈ ∆1 for some R(al) ∈ N . Proof. Recall that N is a proper subgroup of ⟨R(a)⟩ and that n/|N | is odd. Since n is even by Proposition 7.3, it follows that N is of even order, and so the unique involution R(an/2) of ⟨R(a)⟩ is contained in N . As 10 ∈ ∆0 and N ≤ ⟨R(a)⟩ acts on H0 by right multiplication, one has ∆0 = {h0 | h ∈ N}. Since Γ[∆0] is an empty graph, one has an/2 /∈ R. By Proposition 2.3 (1), we have ⟨R ∪ L⟩ = H , and since R and L are both self-inverse, either R ⊆ b⟨a⟩ or L ⊆ b⟨a⟩. By Proposition 2.3 (4), we may assume that R ⊆ b⟨a⟩. Recall that Γ[∆i ∪∆′j ] is a perfect matching for any 0 ≤ i, j ≤ 1. Then 10 is adjacent to r0 ∈ ∆′0 for some r ∈ R. Since R ⊆ b⟨a⟩ and Aut (H) is transitive on b⟨a⟩, by Proposition 2.3 (3), we may assume that r = b. So 10 is adjacent to b0 ∈ ∆′0. Since N ≤ ⟨R(a)⟩ acts on Hi with i = 0 or 1 by right multiplication, we see that the two orbits ∆0,∆ ′ 0 of N are just the form as given in the lemma. Since S = {1}, the edges between H0 and H1 form a perfect matching. This enables us to obtain another two orbits ∆1,∆′1 of N which have the form as given in the lemma. By Lemma 7.9, Γ[∆1∪∆′1] is a perfect matching. So we may assume that 11 is adjacent to (bal)1 ∈ ∆1 for some R(al) ∈ N . Now we shall introduce some new notations which will be used in the following. Assumption V. (1) Let T = ⟨R(al)⟩ be of order t, where al is given in the above lemma. (2) Let Ω0 = {(ai n t )0 | 0 ≤ i ≤ t− 1}, Ω1 = {(bai n t )1 | 0 ≤ i ≤ t− 1}, Ω′0 = {(bai n t )0 | 0 ≤ i ≤ t− 1}, Ω′1 = {(ai n t )1 | 0 ≤ i ≤ t− 1}. (3) B = {BR(h) | h ∈ H}, where B = Ω0 ∪ Ω1. (4) Let B′ = Ω′0 ∪ Ω′1. Then B′ = BR(b). Lemma 7.11. The followings hold. (1) T ≤ N . 194 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 (2) Ω0,Ω1,Ω′0,Ω ′ 1 are four orbits of T . (3) Γ[Ω0 ∪ Ω1 ∪ Ω′0 ∪ Ω′1] is a cycle of length 4t. (4) B is a G-invariant partition of V (Γ). Proof. By Lemma 7.10, we see that R(al) ∈ N , and so T ≤ N . (1) holds. Since T = ⟨R(al)⟩ is assumed to be of order t, one has T = ⟨R(an/t)⟩, and then one can obtain (2). By the adjacency rule of bi-Cayley graph, we can obtain (3). Set Ω = Ω0 ∪ Ω1 ∪ Ω′0 ∪ Ω′1 and B = Ω0 ∪ Ω1. By Lemma 7.8, Γ[∆] is a null graph, and so B = ∆ ∩ Ω. Since Γ has valency 3, it follows that ∆ ∪ ∆′ is a block of imprimitivity of G on V (Γ), and hence Ω is also a block of imprimitivity of G on V (Γ) since Γ[Ω] is a component of Γ[∆ ∪∆′]. Since ∆ is also a block of imprimitivity of G on V (Γ), B(= ∆∩Ω) is a block of imprimitivity of G on V (Γ). Then B = {BR(h) | h ∈ H} is a G-invariant partition of V (Γ). Lemma 7.12. T < N and the quotient graph ΓB of Γ relative to B is isomorphic to the cross ladder graph CL 4n 2t . Moreover, T is the kernel of G acting on B. Proof. Let KB be the kernel of G acting on B. Clearly, T ≤ KB. Let B′ = Ω′0 ∪Ω′1. Then B′ = BR(b) ∈ B. Let BR(h) ∈ B be adjacent to B and BR(h) ̸= B′. Suppose that Γ[B ∪ BR(h)] is a perfect matching. Since G is transitive on B, ΓB is a cycle of length 2nt . Clearly, G/KB is vertex-transitive but not edge-transitive on ΓB, so G/KB ∼= D2n/t. If t = 1, then it is easy to see that Γ ∼= CL4n which is a Cayley graph by Theorem 1.1, a contradiction. If t > 1, then since Γ[Ω] = Γ[B∪B′] is a cycle of length 4t, KB acts faithfully on B, and so KB ≤ Aut (Γ[B ∪B′]) ∼= D8t. Since KB fixes B, one has |KB| | 4t, implying that |G| = |KB| · 2nt | 8n. As |R(H)| = 2n and R(H) is non-normal in G, one has |KB| = 4t due to T ≤ KB. In view of the fact that KB ≲ D8t, KB has a characteristic cyclic subgroup, say J , of order 2t. Then we have J ⊴G because KB ⊴G. Clearly, J is regular on B and J ∩N = T , so JR(H) is regular on V (Γ). It follows from Proposition 2.1 that Γ is a Cayley graph, a contradiction. Therefore, Γ[B∪BR(h)] is not a perfect matching. If N = T , then B = ∆ and B′ = ∆′ are orbits of M , and then Γ[B ∪BR(h)] will be a perfect matching, a contradiction. Thus, N > T. Now we are going to prove that ΓB ∼= CL n2t . Since B is adjacent to B R(h), Ωi is adjacent to ΩR(h)j for some i, j ∈ {0, 1}. Then because Ωi and Ω R(h) j are orbits of T , Γ[Ωi ∪ ΩR(h)j ] is a perfect matching. This implies that ΓB is of valency 3, and so KB is intransitive on B. As every Bh ∈ B is a union of two orbits of T on V (Γ), KB fixes every orbit of T . Since N is cyclic, the normality of N in G implies that T ⊴G. Clearly, Ω0 is adjacent to three pair-wise different orbits of T , so the quotient graph ΓT of Γ relative to T is of valency 3. Consequently, the kernel of G acting on V (ΓT ) is T . Then KB = T . Now R(H)/T ∼= D2n/t is regular on B, and so ΓB is a Cayley graph over R(H)/T . Furthermore, G/T is not arc-transitive on ΓB. Since R(H)/T is non-normal in G/T , ΓB is a non-normal Cayley graph over R(H)/T . If ΓB is arc-transitive, then by [13, Theorem 1], either |Aut (ΓB)| = 3k|R(H)/T | with k ≤ 2, or ΓB has order 2 ·p with p = 3 or 7. For the former, since G/T is not arc-transitive on ΓB, one has |G/T : R(H)/T | ≤ 2, implying R(H)⊴G, a contradiction. For the latter, we have 2nt = 6 or 14, implying n t = 3 or 7. It follows that T is a maximal subgroup of ⟨R(a)⟩, and so T = N , a contradiction. Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 195 Therefore, ΓB is not arc-transitive. Since R(H)/T is non-normal in G/T , by Theorem 1.1, one has ΓB ∼= CL 4n 2t , as required. Proof of Theorem 7.6. By Lemma 7.12, we have ΓB ∼= CL 4n 2t . By the definition of CL 4n 2t , we may partition the vertex set of ΓB in the following way: V (ΓB) = V0 ∪ V1 ∪ · · ·V 2n 2t −2 ∪ V 2n 2t −1 , where Vi = {B0i , B1i }, i ∈ Z 2n2t and E(ΓB) = {{Br2i, Br2i+1}, {Br2i+1, Bs2i+2} | i ∈ Z n2t , r, s ∈ Z2}. Assume that B00 = B and B 0 1 = B ′. Recall that B = Ω0 ∪ Ω1 and B′ = Ω′0 ∪ Ω′1 = BR(b). Moreover, Ω0,Ω1,Ω′0 and Ω ′ 1 are four orbits of T . Then every B j i ∈ B is just a union of two orbits of T . For convenience, we may let Bji = Ω j i0 ∪ Ω j i1, i ∈ Z 2n2t , j ∈ Z2, where Ωji0,Ω j i1 are two orbits of T . For B = B 0 0 , we let Ω0 = Ω 0 00 and Ω1 = Ω 0 01, and for B′ = B01 , we let Ω ′ 0 = Ω 0 10 and Ω ′ 1 = Ω 0 11. For convenience, in the remainder of the proof, we shall use C4t to denote a cycle of length 4t, and we also call C4t a 4t-cycle. Recall that Γ[B ∪ B′] = Γ[B00 ∪ B01 ] ∼= C4t, and that the edges between Ω00i(= Ωi) and Ω 0 1j(= Ω ′ j) form a perfect matching for all i, j ∈ Z2. Since T ⊴ G, the quotient graph ΓT of Γ relative to T has valency 3. So the edges between any two adjacent orbits of T form a perfect matching. From the construction of ΓB, one may see that there exists g ∈ G such that {V0, V1}g = {V2i, V2i+1} for each i ∈ Z n2t . So for each i ∈ Z n2t , r ∈ Z2, we may assume that Γ[B r 2i ∪ Br2i+1] ∼= C4t, and Ωr(2i)s ∼ Ω r (2i+1)t for all s, t ∈ Z2. (Here Ω r (2i)s ∼ Ω r (2i+1)t means that Ωr(2i)s and Ω r (2i+1)t are adjacent in ΓB.) Again, from the construction of ΓB, we may assume that Ω0(2i+2)0 ∼ Ω 0 (2i+1)0,Ω 0 (2i+2)1 ∼ Ω 1 (2i+1)0,Ω 1 (2i+2)1 ∼ Ω 1 (2i+1)0,Ω 1 (2i+2)1 ∼ Ω 0 (2i+1)0, for each i ∈ Z n 2t . We draw a local subgraph of ΓB in Figure 3. Observing that every H HHHH   HH HHH   @ @ @@@ @ @@ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦                             · · · · · · · · · · · · B0−1 B 0 0 B 0 1 B 0 2 B1−1 B 1 0 B 1 1 B 1 2 Ω000 Ω001 Ω010 Ω011 Ω100 Ω101 Ω110 Ω111 Ω1 (−1)0 Ω1 (−1)1 Ω0 (−1)0 Ω0 (−1)1 Ω120 Ω121 Ω020 Ω021 Figure 3: The sketch graph of ΓB Vi = {B0i , B1i } with i ∈ Z 2n2t is a block of imprimitivity of G/KB acting on V (ΓB). So every B0i ∪ B1i with i ∈ Z 2n2t is a block of imprimitivity of G acting on V (Γ). Let E be the kernel of G acting on the block system Λ = {B0i ∪ B1i | i ∈ Z 2n2t }. Then G/E ∼= Dn t 196 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 acts regularly on Λ. Clearly, R(H) is also transitive on Ω, so G/E = R(H)E/E. By Lemma 7.12, T is a the kernel of G acting on B. So E/T is an elementary 2-group. From R(H)/(R(H) ∩ E) ∼= Dn t it follows that R(H) ∩ E = ⟨R(a n2t )⟩ ∼= Z2t, and so (R(H) ∩ E)/T is a normal subgroup of G/T of order 2. This implies that B1i = (B0i ) R(a n 2t ) for i ∈ Z 2n 2t . We may further assume that Ω101 = (Ω 0 00) R(a n 2t ) ⊆ B10 . So Ω000 ∪ Ω101 is just the orbit of ⟨R(a n 2t )⟩ containing 10. Observing that Ω010 ∼ Ω020 and the edges between them are of the form {g0, (baig)0} with g0 ∈ Ω010, one has Ω020 = baiΩ010 = bai(Ω000)R(b) = (Ω000)R(a −i). So Ω120 ⊆ (B10) R(a−i). Since B01 = B ′ = BR(b) = (B00) R(b), one has B11 = (B 1 0) R(b). Recall that 11 ∈ Ω011 = Ω ′ 1 and 11 is adjacent to 10 ∈ Ω000 = Ω0 and (bal)1 ∈ Ω001 = Ω1. As we assume that Ω011 ∼ Ω120, 11 is adjacent to some vertex in Ω120. So Ω120 ⊆ H1 and hence Ω120 = (Ω 1 00) R(a−i) = (Ω001) R(a n 2t )R(a−i) = (Ω001) R(a n 2t −i) = {(bak nt )1 | 0 ≤ k ≤ t− 1}R(a n 2t −i). So we have the following claim. Claim 1 L = {bal, bak nt + n2t−i} and R = {bai, b}, where |R(al)| = t, i ∈ Zn and 0 ≤ k ≤ t− 1. Let G∗10 be the kernel of G10 acting on the neighborhood of 10 in Γ. Then G ∗ 10 ≤ E10 . Recall that for each i ∈ Z n 2t , r ∈ Z2, Γ[Br2i ∪ Br2i+1] ∼= C4t and the edges between B02i+1∪B12i+1 and B02i+2∪B12i+2 form a perfect matching. It follows that E acts faithfully on each B0i ∪B1i . Clearly, G∗10 ≤ E10 , so G ∗ 10 acts faithfully on each B 0 i ∪B1i . Claim 2 If t > 2 then G∗10 = 1, and if t = 2 then G ∗ 10 ≤ Z2 and 3 | n. Assume that t ≥ 2. Since Γ[B00 ∪ B01 ] ∼= C4t, G∗10 fixes every vertex in B 0 0 , and so fixes every vertex in Ω0(−1)0 since Ω 0 (−1)0 ∼ Ω 0 00 (see Figure 3). This implies that G ∗ 10 fixes Ω0(−1)1 setwise, and so fixes Ω 1 00 setwise since Ω 0 (−1)1 ∼ Ω 1 00. Consequently, G ∗ 10 also fixes Ω101 setwise. Similarly, by considering the edges between B 0 1 ∪B11 and B02 ∪B12 , we see that G∗10 fixes both Ω 1 10 and Ω 1 11 setwise. Recall that the edges between Ω 1 0i and Ω 1 1j form a perfect matching for i, j ∈ Z2. As Γ[B01 ∪ B11 ] ∼= C4t, G∗10 acts faithfully on Ω 1 00 (or Ω101), and so G ∗ 10 ≤ Z2. If t > 2, then since Γ[B0−2 ∪B0−1] ∼= C4t, G∗10 will fix every vertex in this cycle, and in particular, G∗10 will fix every vertex in Ω 0 (−1)1. As Ω 0 (−1)1 ∼ Ω 1 00, G ∗ 10 will fix every vertex in Ω100. Since G ∗ 10 acts faithfully on Ω 1 00, one has G ∗ 10 = 1. Let t = 2. We shall show that 3 | n. Then T = ⟨R(an2 )⟩. Recall that (R(H)∩E)/T is a normal subgroup of G/T of order 2. Let M = R(H)∩E. Then M is a normal subgroup of G of order 4. Since R(H) is dihedral, one has M = ⟨R(an4 )⟩. Let C = CG(M). Then R(a) ∈ C and R(b) /∈ C. It follows that C is a proper subgroup of G. Since G/E acts regularly on Λ, C10 fixes every element in Λ. Since C10 centralizes M , C10 fixes every vertex in the orbit Ω000 ∪ Ω101 of M containing 10. Clearly, C10 ≤ G10 , so C10/(C10 ∩G∗10) ≤ Z2. As we have shown that G ∗ 10 acts faithfully on Ω 1 01, it follows that Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 197 C10 ∩G∗10 = 1 since C10 fixes Ω 1 01 pointwise, and hence C10 ≤ Z2. On the other hand, as G∗10 ≤ Z2, one has |G| | 4 · 4n = 16n. Since C < G and R(a) ∈ C, one has |C| = kn with k | 8. Suppose that 3 ∤ n. For any odd prime divisor p of n, let P be a Sylow p-subgroup of ⟨R(a)⟩. Then P is also a Sylow p-subgroup of C. If P is not normal in C, then by Sylow’s theorem, we have |C : NC(P )| = k′p + 1 | 8 for some integer k′. Since p ̸= 3, one has p = 7 and k′ = 1. This implies that |C| = 8|NC(P )|, and so |C| = 8n due to R(a) ∈ C and C < G. Since C10 ≤ Z2, one has |C : C10 | ≥ 4n, and so C is transitive on V (Γ). Moreover, we have CC(P ) = NC(P ) = ⟨R(a)⟩. By Burnside theorem, C has a normal subgroup M such that C = M ⋊ P . Then the quotient graph ΓM of Γ relative to M would be a cycle of length |P |, and the subgraph induced by each orbit of M is just a perfect matching. This implies that M is just the kernel of G acting on V (ΓM ). Furthermore, C/M is a vertex-transitive subgroup of Aut (ΓM ). Since ΓM is a cycle, C/M must contain a subgroup, say B/M acting regularly on V (ΓM ). Then B will be regular on V (Γ), and so by Proposition 2.1, Γ is a Cayley graph, a contradiction. Therefore, P ⊴ C, and since C ⊴G, one has P ⊴G, implying P ≤ N . By the arbitrariness of P , n/|N | must be even, contrary to Lemma 7.7. Thus, 3 | n, as claimed. The following claim shows that t = 1 or 2. Claim 3 t ≤ 2. By way of contradiction, suppose that t > 2. Let C = CG(T ). Then ⟨R(a)⟩ ≤ C and R(H) ≰ C since |T | = t > 2. Clearly, C10 ≤ E10 . As C10 centralizes T , C10 will fixes every vertex in Ω000 since Ω 0 00 is an orbit of T containing 10. Since Γ[B 0 0 ∪ B01 ] ∼= C4t, C10 fixes every vertex in this 4t-cycle, and so C10 ≤ G∗10 = 1 (by Claim 2). Thus, C acts semiregularly on V (Γ). If C = ⟨R(a)⟩, then by N/C-theorem, we have G/⟨R(a)⟩ = G/C ≤ Aut (T ). Since T ≤ N ≤ ⟨R(a)⟩ is cyclic, Aut (T ) is abelian. It then follows that R(H)/C ⊴ G/C, and hence R(H) ⊴ G, a contradiction. If C > ⟨R(a)⟩, then |C| = 2n because Γ is non-Cayley. Since H0 and H1 are not blocks of imprimitivity of G on V (Γ), C does not fix H0 setwise, and so R(H)C is transitive on V (Γ). Clearly, R(H) ∩ C = ⟨R(a)⟩, so |R(H)C| = |R(H)||C|/|⟨R(a)⟩| = 4n. It follows that R(H)C is regular on V (Γ), contradicting that Γ is non-Cayley. By Claim 3, we only need to consider the following two cases: Case 1 t = 1. In this case, by Claim 1, we have R = {b, bai} and L = {b, ban2 −i}. For convenience, we let n = 2ℓ. Then R = {b, bai} and L = {b, baℓ−i}. By Proposition 2.3 (1), the connectedness of Γ implies that ⟨ai, aℓ⟩ = ⟨a⟩. Then either (i, 2ℓ) = 1, or i = 2k with (k, 2ℓ) = 1 and ℓ is odd. Recall that H = ⟨a, b | a2ℓ = b2 = 1, bab = a−1⟩. For any λ ∈ Z∗2ℓ, let αλ be the automorphism of H induced by the map aλ 7→ a, b 7→ b. So if (i, 2ℓ) = 1, then we have (R,L)αi = ({b, ba}, {b, baℓ−1}), and if i = 2k with (k, 2ℓ) = 2 and ℓ is odd, then we have (R,L)αk = ({b, ba2}, {b, baℓ−2}). 198 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 So by Proposition 2.3 (3), we have (R,L, S) ≡ ({b, ba}, {b, baℓ−1}, {1}) or ({b, ba2}, {b, baℓ−2}, {1})(ℓ is odd). Suppose that ℓ is even. Then (R,L, S) ≡ ({b, ba}, {b, baℓ−1}, {1}). Since ℓ is even, one has (2ℓ, ℓ+1) = 1 and (ℓ+1)2 ≡ 1 (mod 2ℓ). Then it is easy to check that αℓ+1 is an automorphism of H of order 2 that swaps {b, ba} and {b, baℓ−1}. By Proposition 2.4, we have δαℓ+1,1,1 ∈ I , and then Γ ∼= BiCay(H, {b, ba}, {b, baℓ+1}, {1}) is a Cayley graph, a contradiction. Now we assume that n = 2ℓ with ℓ = 2m+ 1 for some integer m. Let Γ1 = BiCay(H, {b, ba}, {b, ba2m}, {1}),Γ2 = BiCay(H, {b, ba2}, {b, ba2m−1}, {1}). Direct calculation shows that (n, 2m − 1) = 1, and 2m(2m − 1) ≡ 2 (mod n). Then the automorphism α2m−1 : a 7→ a2m−1, b 7→ b maps the pair of two subsets ({b, ba}, {b, ba2m}) to ({b, ba2m−1}, {b, ba2}). So, we have (R,L, S) ≡ ({b, ba}, {b, ba2m}, {1}). By Lemma 4.1 and Theorem 1.2, Γ ∼= MCL(4m, 2) and Γ is non-Cayley if and only if 3 ∤ (2m + 1). Note that 3 ∤ (2m + 1) is equivalent to m ̸≡ 1 (mod 3). So we obtain the first family of graphs in Theorem 7.6. Case 2 t = 2. In this case, by Claim 1, we have R = {b, bai} and L = {ban2 , ba 3n4 −i} or {ban2 , ba n 4 −i}. We still use the following notation: For any λ ∈ Z∗2ℓ, let αλ be the automorphism of H induced by the map aλ 7→ a, b 7→ b. Note that ({b, bai}, {ban2 , ba 3n4 −i})α−1 = ({b, ba−i}, {ban2 , ban4 −(−i)}). By replacing −i by i, we may always assume that (R,L) = ({b, bai}, {ban2 , ban4 −i}). By Claim 2, we have 3 | n. So we may assume that n = 12m for some integer m. Then we have (R,L) = ({b, bai}, {ba6m, ba3m−i}). Since Γ is connected, by Proposition 2.3, we have ⟨ai, a3m⟩ = ⟨a⟩. If m is odd, by Lemma 6.1, Γ will be a Cayley graph which is impossible. Thus, m is even. It then follows that ⟨ai⟩ ∩ ⟨a3m⟩ > 1 since ⟨ai, a3m⟩ = ⟨ai⟩⟨a3m⟩ = ⟨a⟩. Since ⟨a3m⟩ ∼= Z4, one has |⟨ai⟩ ∩ ⟨a3m⟩| = 2 or 4. For the former, we would have |⟨ai⟩| = 6m, and since m is even, one has 4 | |⟨ai⟩|, and hence a3m ∈ ⟨ai⟩, a contradiction. Thus, we have |⟨ai⟩ ∩ ⟨a3m⟩| = 4, that is, ⟨ai⟩ = ⟨a⟩. So (i, 12m) = 1, and then αi ∈ Aut (H) which maps ({b, bai}, {ba6m, ba3m−i}) to ({b, ba}, {ba6m, ba3m−1}) or ({b, ba}, {ba6m, ba−3m−1}). Then (R,L, S) ≡ ({b, ba}, {ba6m, ba3m−1}, {1}) or ({b, ba}, {ba6m, ba−3m−1}), {1}. If m ≡ 2 (mod 4), then by Lemma 6.2, we see that Γ will be a Cayley graph, a con- tradiction. Thus, m ≡ 0 (mod 4). Clearly, (3m − 1, 12m) = 1, and hence the map a 7→ a3m−1, b 7→ ba6m induces an automorphism, say β of H . It is easy to check that ({b, ba}, {ba6m, ba3m−1})β = ({ba6m, ba−3m−1}, {b, ba}). Mi-Mi Zhang and Jin-Xin Zhou: Trivalent dihedrants and bi-dihedrants 199 Thus, (R,L, S) ≡ ({b, ba}, {ba6m, ba3m−1}, {1}). By Proposition 5.1, Γ is a non-Cayley graph. Let m = 4ℓ for some integer ℓ. Then n = 48ℓ and then we get the second family of graphs in Theorem 7.6. This completes the proof of Theorem 7.6. 7.4 Proof of Theorem 1.3 By [20, Theorem 1.2], if Γ is 0- or 1-type, then Γ is a Cayley graph. Let Γ be of 2- type. Suppose that Γ is a non-Cayley graph. Let G ≤ Aut (Γ) be minimal subject to that R(H) ≤ G and G is transitive on V (Γ). If Γ is arc-transitive or H0 and H1 are blocks of imprimitivity of G on V (Γ), then by [20, Theorem 1.1] and Proposition 7.2, we obtain the graphs in part (1)–(3) of Theorem 1.3. Otherwise, Γ is not arc-transitive and H0 and H1 are not blocks of imprimitivity of G on V (Γ), by Theorem 7.6, we obtain the last two families of graphs of Theorem 1.3. ORCID iDs Mi-Mi Zhang https://orcid.org/0000-0002-8719-5888 Jin-Xin Zhou https://orcid.org/0000-0002-8353-896X References [1] M. Alaeiyan, M. Ghasemi and G. R. Safakish, The normality of cubic Cayley graphs for dihedral groups, Vietnam J. Math. 37 (2009), 43–48, http://www.math.ac.vn/ publications/vjm/VJM_37/43.htm. [2] N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993. [3] J. Bondy and U. Murty, Graph Theory with Applications, Elsevier Science Ltd/North-Holland, 1976. [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, computational algebra and number theory (London, 1993). [5] P. Cameron, J. Sheehan and P. Spiga, Semiregular automorphisms of vertex-transitive cubic graphs, European J. Combin. 27 (2006), 924–930, doi:10.1016/j.ejc.2005.04.008. [6] E. Dobson, A. Malnič, D. Marušič and L. A. Nowitz, Semiregular automorphisms of vertex- transitive graphs of certain valencies, J. Combin. Theory Ser. B 97 (2007), 371–380, doi:10. 1016/j.jctb.2006.06.004. [7] S. Du, A. Malnič and D. Marušič, Classification of 2-arc-transitive dihedrants, J. Combin. Theory Ser. B 98 (2008), 1349–1372, doi:10.1016/j.jctb.2008.02.007. [8] R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211–218, doi:10.1017/s0305004100049811. [9] C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981), 243–256, doi:10.1007/bf02579330. [10] C. D. Godsil, The automorphism groups of some cubic Cayley graphs, European J. Combin. 4 (1983), 25–32, doi:10.1016/s0195-6698(83)80005-5. [11] I. Kovács, B. Kuzman, A. Malnič and S. Wilson, Characterization of edge-transitive 4-valent bicirculants, J. Graph Theory 69 (2012), 441–463, doi:10.1002/jgt.20594. 200 Ars Math. Contemp. 21 (2021) #P2.02 / 175–200 [12] D. Marušič, On 2-arc-transitivity of Cayley graphs, J. Combin. Theory Ser. B 87 (2003), 162– 196, doi:10.1016/s0095-8956(02)00033-3, dedicated to Crispin St. J. A. Nash-Williams. [13] D. Marušič and T. Pisanski, Symmetries of hexagonal molecular graphs on the torus, Croat. Chem. Acta 73 (2000), 969–981, https://hrcak.srce.hr/131972. [14] R. Nedela and M. Škoviera, Which generalized Petersen graphs are Cayley graphs?, J. Graph Theory 19 (1995), 1–11, doi:10.1002/jgt.3190190102. [15] T. Pisanski, A classification of cubic bicirculants, Discrete Math. 307 (2007), 567–578, doi: 10.1016/j.disc.2005.09.053. [16] P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Comput. 50 (2013), 465–477, doi:10.1016/j.jsc.2012.09.002. [17] M. E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combinatorial Theory 6 (1969), 152–164. [18] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964. [19] M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309–319, doi:10.1016/s0012-365x(97)00152-0, graph theory (Lake Bled, 1995). [20] M.-M. Zhang and J.-X. Zhou, Trivalent vertex-transitive bi-dihedrants, Discrete Math. 340 (2017), 1757–1772, doi:10.1016/j.disc.2017.03.017. [21] W.-J. Zhang, Y.-Q. Feng and J.-X. Zhou, Cubic vertex-transitive non-Cayley graphs of order 12p, Sci. China Math. 61 (2018), 1153–1162, doi:10.1007/s11425-016-9095-8. [22] C. Zhou and Y.-Q. Feng, Automorphism groups of connected cubic Cayley graphs of order 4p, Algebra Colloq. 14 (2007), 351–359, doi:10.1142/s100538670700034x. [23] J.-X. Zhou and Y.-Q. Feng, Cubic vertex-transitive non-Cayley graphs of order 8p, Electron. J. Combin. 19 (2012), Paper 53, 13, doi:10.37236/2087. [24] J.-X. Zhou and Y.-Q. Feng, Cubic bi-Cayley graphs over abelian groups, European J. Combin. 36 (2014), 679–693, doi:10.1016/j.ejc.2013.10.005. [25] J.-X. Zhou and Y.-Q. Feng, The automorphisms of bi-Cayley graphs, J. Combin. Theory Ser. B 116 (2016), 504–532, doi:10.1016/j.jctb.2015.10.004. [26] J.-X. Zhou and M. Ghasemi, Automorphisms of a family of cubic graphs, Algebra Colloq. 20 (2013), 495–506, doi:10.1142/s1005386713000461.