Back
 JAMP  Vol.8 No.12 , December 2020
Automorphism Groups of Cubic Cayley Graphs of Dihedral Groups of Order 2npm (n ≥ 2 and p Odd Prime)
Abstract:

1. Introduction

An automorphism of a graph X is a permutation σ of vertex set of X with the property that, for any vertices u and v, we have { u σ , v σ } is an edge of X if and only if { u , v } is the edge of X. As usual, we use u σ to denote the image of the vertex u under the permutation σ and { u , v } to denote the edge joining vertices u and v. All automorphisms of graph X form a group under the composite operation of mapping. This group is called the full automorphism group of graph X, denoted by A in this paper.

For a graph X, we denote vertex set and edge set of X by V ( X ) and E ( X ) . A v is the stabilizer of vertex v in the automorphism group of X. X k ( v ) denotes the set of vertices at distance k from vertex v. D 2 n means the dihedral group of order 2n. A graph is called vertex-transitive if its automorphism group A is transitive on the vertex set V ( X ) . An s-arc in a graph is an ordered ( s + 1 ) -tuple ( v 0 , v 1 ,..., v s 1 , v s ) of vertices of the graph such that v i 1 is adjacent to v i for 1 i s and v i 1 v i + 1 for 1 i s . A graph is said to be s-arc-transitive if the automorphism group A acts transitively on the set of all s-arcs in X. When s = 1 , 1-arc called arc and 1-arc transitive is called arc-transitive or symmetric.

Throughout this paper, graphs are finite, simple and undirected.

Let G be a finite group and S be a subset of G such that 1 S . The Cayley graph X = C a y ( G , S ) on G with respect to S is defined to have vertex set V ( X ) = G and edge set E ( X ) = { { g , s g } | g G and s S } . Let set S 1 = { s 1 | s S } . If S 1 = S , C a y ( G , S ) is undirected. If S is a generating system of G, C a y ( G , S ) is connected. Two subsets S and T of group G are called equivalent if there exists a group automorphism of group G mapping S to T: S α = T for some α A u t ( G ) . Denote by S T . If S and T are equivalent, Cayley graphs C a y ( G , S ) and C a y ( G , S ) are isomorphic.

The right regular representation R ( G ) of group G is a subgroup of the the automorphism group A of the Cayley graph X. In particular by [1], if R ( G ) is the full automorphism group of X then X = C a y ( G , S ) is called a GRR (for graphical regular representation) of G. A Cayley graph is normal if R ( G ) is a normal subgroup of A. R ( G ) is transitive on G hence Cayley graph is vertex-transitive. Denote A u t ( G , S ) = { α A u t ( G ) | S α = S } , the set of all automorphism of group G preserving S. A u t ( G , S ) is also a subgroup of the automorphism group of Cayley graph. In particular, A u t ( G , S ) is a subgroup of stabilizer of vertex identity A 1 . By [2] the normalizer of R ( G ) in A is the semi-direct product of R ( G ) and A u t ( G , S ) : N A ( R ( G ) ) = R ( G ) A u t ( G , S ) . By [3] Proposition 1.5 X is normal if and only if A 1 = A u t ( G , S ) . Cayley graph X is normal if and only if the automorphism group of X is A = R ( G ) A u t ( G , S ) . Normality provides an approach to find automorphism groups of Cayley graphs.

In [4] the automorphism group of connected cubic Cayley graphs of order 4p is given. In [5] the automorphism group of connected cubic Cayley graphs of order 32p is given. In this paper, the automorphism group of connected cubic Cayley graphs of dihedral groups of order 2 n p m where n 2 and p is odd is given.

Summarising theorem 4.1, 4.2, 4.3 in Part 4 gives the main results.

Theorem 1.1. Let G = D 2 n p m be a dihedral group where n 2 and p is an odd prime number. S is an inverse-closed generating system of three elements without identity element. Then Cayley graph C a y ( G , S ) is GRR except the following cases:

1) S { b , a b , a k b } where k 2 1 ( mod 2 n 1 p m ) and gcd ( k ,2 n 1 p m ) = 1 , A u t ( X ) G : 2 .

2) S { b , a b , a 2 n 1 p m b } , A u t ( X ) 2 2 n 2 p m D 2 n 1 p m .

3) S { a , a 1 , b } , A u t ( X ) = G : 2 .

4) S { b , a b , a 2 n 2 p m } , A u t ( X ) = G : 2 .

2. Preliminary

Results used to prove main theorem are listed here.

Proposition 2.1. Suppose that G = < a , b | a n = b 2 = 1 , b 1 a b = a 1 > is a dihedral group, then the automorphism group A u t ( G ) of G has the following properties.

1) Any automorphism of G can be defined as a a i and b a j b where i n * and j n .

2) A u t ( G ) = < α > < β > n n * where α : a a , b a b ; β : a a i , b b , i n * .

Proposition 2.2. Suppose G is a finite group and subsets S T , then C a y ( G , S ) C a y ( G , T ) .

Proposition 2.3. Let G = < a , b | a n = b 2 = 1 , b 1 a b = a 1 > be the dihedral group of order 2n. Subsets { b , a b , a k b } { b , a b , a 1 k b } .

Proof Let σ A u t ( G ) : a a 1 , b a b then { b , a b , a k b } σ = { b , a b , a 1 k b } .

The following sufficient and necessary condition of normality of Cayley graph is from paper [6].

Proposition 2.4. Let X = C a y ( G , S ) be connected. Then X is a normal Cayley graph of G if and only if the following conditions are satisfied:

1) For each φ A 1 there exists σ A u t ( G ) such that φ | X 1 ( 1 ) = σ | X 1 ( 1 ) ;

2) For each φ A 1 , φ | X 1 ( 1 ) = 1 X 1 ( 1 ) implies φ | X 2 ( 1 ) = 1 X 2 ( 1 ) .

A classification of locally primitive Cayley graphs of dihedral groups from paper [7] will be used.

Proposition 2.5. Let X be a locally-primitive Cayley graph of a dihedral group of order 2n. Then one of the following statements is true, where q is a prime power.

1) X is 2-arc-transitive, and one of the following holds:

a) X = K 2 n , K n , n or K n , n n K 2 ;

b) X = H D ( 11,5,2 ) or H D ( 11,6,2 ) , the incidence or non-incidence graph of the Hadamard design on 11 points;

c) X = P H ( d , q ) or P H ( d , q ) , the point-hyperplane incidence or non-incidence graph of ( d 1 ) -dimension projective geometry P G ( d 1, q ) , where d 3 ;

d) X = K q + 1 2 d , where d is a divisor of q 1 2 if q 1 (mod 4), and a divisor of q 1 if q 3 (mod 4) respectively.

2) X = N D 2 n , r , k is a normal Cayley graph and is not 2-arc-transitive, where n = r t p 1 e 1 p 2 e 2 p s e s 13 with r , p 1 , p 2 , , p s distinct odd primes, t 1 , s 1 and r | ( p i 1 ) for each i. There are exactly ( r 1 ) s 1 non-isomorphism such graphs for a given order 2n.

3. Lemmas and Propositions

In the following, group G means that G = < a , b | a 2 n 1 p m = b 2 = 1 , b 1 a b = a 1 > be dihedral group of order 2 n p m where n 2 and p is an odd prime number.

Proposition 3.1. If S = { a i b , a j b , a r b } is a generating system of G of three elements, then S { b , a b , a k b } for some 2 k 2 n 1 p m 1 .

There are two types of S classified by the number of subsets of two elements generating G.

Type 1: S has only one subset of two elements generating G.

Type 2: S has exactly two subsets of two elements generating G. In this case, S { b , a b , a k b } where gcd ( k ,2 n 1 p m ) = 1 .

The proof of Proposition 3.1 will be done by the following three lemmas.

Lemma 3.1. If S = { a i b , a j b , a r b } is a generating system of G of three elements, then S is equivalent to a subset of type { b , a b , a k b } for some 2 k 2 n 1 p m 1 .

Proof By proposition 2.1 in preliminary, automorphism group Aut(G) of dihedral group G is transitive on the set of involutions { a i b | 0 i 2 n 1 p m 1 } . One may assume that b S and S = { b , a i b , a j b } be a generating system of G of three elements. S has three subsets of two elements: { b , a i b } , { b , a j b } and { a i b , a j b } ..

Note that, subset T G is a generating system of G if and only if T α is a generating system of G for any α A u t ( G ) .

Suppose that subset { b , a x b } ( x = i or j ) generates G. Let α A u t ( G ) : a a x , b b , then { b , a b , a k b } α = { b , a i b , a j b } for some k 0,1 . Hence S { b , a b , a k b } .

Assume that both subset { b , a i b } and { b , a j b } do not generate G. Next will show that { a i b , a j b } must be able to generate G.

G = < S > = < b , a i b , a j b > = < a i , a j > < b > = < a gcd ( i , j ) > < b > . Hence gcd ( i , j ) and 2 n 1 p m are mutually prime.

G < b , a i b > = < a i > < b > . Hence i and 2 n 1 p m are not mutually prime.

Similarly, G < b , a j b > implies that j and 2 n 1 p m are also not mutually prime.

( gcd ( i , j ) , 2 n 1 p m ) = 1 , ( i ,2 n 1 p m ) 1 and ( j ,2 n 1 p m ) 1 imply that, for i and j , one number is power of 2 and the other one is power of p. Thus i j and 2 n 1 p m are mutually prime.

Hence, { a i b , a j b } is a generating system of G since < a i b , a j b > = < a i j > < a i b > = G .

Let α A u t ( G ) : a a i j , b a j b . Then { b , a b , a k b } α = { b , a i b , a j b } for some k. S { b , a b , a k b } .

Corollary 3.1. If S = { a i b , a j b , a r b } is a generating system of G of three elements, there exists at least one subset of two elements generating G.

Lemma 3.2. If S = { a i b , a j b , a r b } is a generating system of G of three elements, there are only one or two subsets of two elements of S generating G.

Proof By Lemma 3.1, we assume that S = { b , a b , a k b } where k 0,1 . S has three subsets of two elements: { b , a b } , { b , a k b } and { a b , a k b } . Next we will show that it is impossible that all three subsets of two elements generating G.

< b , a k b > = < a k > < b > is a dihedral subgroup of G. < a b , a k b > = < a k 1 > < a b > is also a dihedral subgroup of G.

For k and k 1 , one is an even number and the other one is an odd number. The orders of elements a k and a k 1 are different: ( a k ) ( a k 1 ) . This implies that at least one subset of { b , a k b } and { a b , a k b } does not generate G.

Hence there are only one or two subsets of two elements of S generating G.

Lemma 3.3. Let S = { a i b , a j b , a r b } be a generating system of G of three elements and S has two subsets of two elements generating G. If S { b , a b , a k b } , either gcd ( k ,2 n 1 p m ) = 1 or gcd ( 1 k ,2 n 1 p m ) = 1 .

Proposition 3.2. Suppose that S = { a i b , a j b , a r b } is a generating system of G of three elements and S { b , a b , a k b } .

(1) If S has only one subset of two elements generating G, then A u t ( G , S ) = 1 .

(2) If S has two subsets of two elements generating G, then A u t ( G , S ) = 1 except the following two cases. A u t ( G , S ) 2 if k 2 1 ( mod 2 n 1 p m ) and gcd ( k ,2 n 1 p m ) = 1 ; A u t ( G , S ) 2 if ( 1 k ) 2 1 ( mod 2 n 1 p m ) and gcd ( 1 k ,2 n 1 p m ) = 1 .

Proof (1) If there is only one subset of two elements in S = { b , a b , a k b } generating G, then G < b , a k b > , G < a b , a k b > and G = < b , a b > . For any σ A u t ( G , S ) , { b , a b } σ is also a generating system of G. { b , a b } σ = { b , a b } . Since S σ = S . Hence a k b = S { b , a b } is fixed by σ . ( a k b ) σ = a k b .

If b σ = b and ( a b ) σ = a b then a σ = ( a b b ) σ = ( a b ) σ b σ = a b b = a , hence σ = 1 .

If b σ = a b and ( a b ) σ = b , then a σ = ( a b b ) σ = ( a b ) σ b σ = b a b = a 1 . This implies that a k b = ( a k b ) σ = ( a k ) σ b σ = a k a b = a 1 k b . Thus a k = a 1 k . This is a contradiction. For k and 1 k , one is an even number and the other one is an odd number. This implies that the orders of the element a k and a 1 k are not equal: ( a k ) ( a 1 k ) .

Hence A u t ( G , S ) = 1 .

(2) If there are two subsets of two elements of S generating G, we assume that gcd ( k , 2 n 1 p m ) = 1 . G = < b , a b > = < b , a k b > and G < a b , a k b > .

Since subset { a b , a k b } is the only subset of two elements not generating G, { a b , a k b } σ = { a b , a k b } for any σ A u t ( G , S ) . b = S { a b , a k b } is fixed by σ . ( a b ) σ = a b or a k b .

If ( a b ) σ = a b , then σ = 1 .

If ( a b ) σ = a k b , then a σ = ( a b b ) σ = ( a b ) σ b σ = a k b b = a k . ( a k b ) σ = ( a k ) σ b σ = ( a k ) k b = a k 2 b = a b . So k 2 1 ( mod 2 n 1 p m ) .

Hence A u t ( G , S ) = 1 if k 2 1 ( mod 2 n 1 p m ) . A u t ( G , S ) 2 if k 2 1 ( mod 2 n 1 p m ) .

Similarly, when gcd ( 1 k , 2 n 1 p m ) = 1 , A u t ( G , S ) = 1 if ( 1 k ) 2 1 ( mod 2 n 1 p m ) . A u t ( G , S ) 2 if ( 1 k ) 2 1 ( mod 2 n 1 p m ) .

Proposition 3.3. Suppose that S is inverse-closed generating system of three elements of G, then S { a , a 1 , b } , { b , a b , a 2 n 2 p m } or { b , a b , a k b } ( k 0,1 ) .

Proof Since S contains three elements and inverse-closed, there must be an involution in S. There are two orbits of involutions in G under the action of group automorphism A u t ( G ) : { a 2 n 2 p m } and { a i b | 0 i 2 n 1 p m 1 } .

Suppose that a 2 n 2 p m S . S { a 2 n 2 p m } is also inverse-closed hence it is a set of two involutions from orbit { a i b | 0 i 2 n 1 p m 1 } . S generating G implies that S { a 2 n 2 p m } also generates G. We get S { b , a b , a 2 n 2 p m } .

Suppose that S contains an involution from { a i b | 0 i 2 n 1 p m 1 } . A u t ( G ) is transitive on this orbit, we can assume that b S . If S { b } contains an involution, S { b , a b , a k b } ( k 0,1 ) by Proposition 3.1 and 2.1. If S { b } contains no involutions, S { b , a , a 1 } by Proposition 2.1.

4. Results

By Proposition 3.3, we only need to discuss X = C a y ( G , S ) for S = { a , a 1 , b } , { b , a b , a 2 n 2 p m } and { b , a b , a k b } ( k 0,1 ) .

Firstly, we discuss X = C a y ( G , { b , a b , a k b } ) ( k 0,1 ) .

Theorem 4.1. Suppose that S = { a i b , a j b , a m b } is a generating system of three involutions of G and S { b , a b , a k b } .

X is GRR except the following cases.

(1) When gcd ( k ,2 n 2 p m ) = 1 , k 2 1 ( mod 2 n 1 p m ) and k 2 n 2 p m + 1 then A u t ( X ) R ( G ) : 2 .

(2) When gcd ( 1 k ,2 n 2 p m ) = 1 , ( 1 k ) 2 1 ( mod 2 n 1 p m ) and k 2 n 2 p m then A u t ( X ) R ( G ) : 2 .

(3) If k = 2 n 2 p m + 1 or k = 2 n 2 p m , then A u t ( X ) 2 2 n 2 p m D 2 n 1 p m .

Proof Let S = { b , a b , a k b } where 2 k 2 n 1 p m 1 and X = C a y ( G , S ) . Classify X in two cases: there are 4-cycles in X and there is no 4-cycle in X.

(1) Note that X 2 ( 1 ) = { a , a k , a 1 , a k 1 , a k , a 1 k } is the set of vertices at distance 2 from vertex 1.

If there are 4-cycles in X, some vertices in X 2 ( 1 ) are coincident. Solving a = a k 1 and a 1 = a 1 k we get k = 2 . Solving a = a k and a k = a 1 we get k = 1 . Solving a k = a k we get k = 2 n 2 p m . Solving a k 1 = a 1 k we get k = 2 n 2 p m + 1 . There is no solution for other equations. Note that −1 and 2 n 2 p m + 1 are two solutions of equation k 2 1 ( mod 2 n 1 p m ) . 2 and 2 n 2 p m are two solutions of equation ( 1 k ) 2 1 ( mod 2 n 1 p m ) . Since { b , a b , a 2 b } { b , a b , a 1 b } and { b , a b , a 2 n 2 p m b } { b , a b , a 2 n 2 p m + 1 b } we only discuss k = 2 and k = 2 n 2 p m .

(1.1) When k = 2 , X = C 2 n 1 p m × K 2 is a cylinder as Figure 1. Hence A D 2 n p m × 2 .

(1.2) When k = 2 n 2 p m , X is a thickened 2-cover of the cycle graph C 2 n 1 p m as Figure 2. All 4-cycles in X form an imprimitive block system of A and the

Figure 1. X = C a y ( G , { b , a b , a 2 b } ) .

Figure 2. X = C a y ( G , { b , a b , a 2 n 2 p m b } ) .

kernel of the action of A on the imprimitive block system is isomorphic to 2 2 n 2 p m . Thus A Z 2 2 n 2 p m D 2 n 1 p m .

(2) Suppose that there is no 4-cycle in X. We will count 6-cycles passing through vertex 1.

X 3 ( 1 ) = { a k b , a 1 b , a 1 k b , a 2 k b , a k 1 b , a k + 1 b , a 2 b , a 2 k 1 b , a 2 k b } is the set of

vertices at distance 3 from vertex 1.

a) Solving a 2 k b = a 2 k b and a 2 k 1 b = a 1 k b , we get 3 k 2 ( mod 2 n 1 p m ) . Solving a 2 k b = a 1 k b and a 2 k 1 b = a k b , we get 3 k 1 ( mod 2 n 1 p m ) . Solving a k 1 b = a 2 b and a 1 b = a 2 k b we get k = 3 . Solving a k = a 2 and a k + 1 = a 1 we get k = 2 . There is no solution for other equations.

The induced subgraph of the set of vertices at distance less than or equal to 3 from vertex 1 in X are isomorphic in these four cases. The following uses C a y ( G , { b , a b , a 3 b } ) as representative to discuss. See Figure 3.

We count the number of 6-cycles passing through vertex 1. There are four 6-cycles through edge { 1, b } . There are five 6-cycles through edge { 1, a b } . There are three 6-cycles through edge { 1, a 3 b } . For any σ A 1 , A 1 fixes edged { 1, b } , { 1, a b } , { 1, a 3 b } and hence σ fixes vertices set X 1 ( 1 ) = { b , a b , a 3 b } pointwise. σ fixes all vertices on X by the connectivity of X and the transitivity of A on V ( X ) . Hence A 1 = 1 . X is GRR.

b) Suppose that k 3 , k 2 , 3 k 2 , 3 k 1 (mod 2 n 1 p m ). Then the induced subgraph of the set of vertices at distance less than or equal to 3 from vertex 1 in X is the as Figure 4.

Firstly, show that the action of A 1 on X 1 ( 1 ) is faithful.

Let σ A 1 and σ fixes X 1 ( 1 ) pointwise. Passing through vertices { 1, b , a b } ,

Figure 3. X = inducedsubgraphof C a y ( G , { b , a b , a 3 b } ) .

Figure 4. X = inducedsubgraph C a y ( G , { b , a b , a k b } ) .

there is a unique 6-cycle [ 1 , b , a k , a 1 k b , a k 1 , a b ] C 1 . Passing through vertices { 1, b , a k b } , there is a unique 6-cycle [ 1 , b , a , a k 1 b , a 1 k , a k b ] C 2 . Passing through vertices { 1, a b , a k b } , there is a unique 6-cycle [ 1 , a b , a 1 , a k + 1 b , a k , a k b ] C 3 . For any α A , the image of a cycle of length l under α is also a cycle of length l. Note that σ A 1 fixes { 1, b , a b , a k b } pointwise, hence C 1 σ is also a 6-cycle passing through vertices 1, b , a b . Hence C 1 σ = C 1 . Follow the same argument, C 2 σ = C 2 , C 3 σ = C 3 . So σ fixes all vertices on cycles C 1 , C 2 , C 3 . In particular, σ fixes X 2 ( 1 ) pointwise. By the connectivity of X and the transitivity of A on V ( X ) , we get A 1 acts on X 1 ( 1 ) = S faithfully.

Next, show that X is normal.

A 1 acting on X 1 ( 1 ) faithfully implies that A 1 is isomorphic to a subgroup of symmetric group of degree 3. A 1 S 3 .

If A 1 A 3 or S 3 , then A 1 is transitive on X 1 ( 1 ) . Since | X 1 ( 1 ) | = 3 is prime, X is a locally-primitive Cayley graph. Theorem 1.5 in [7] gives a classification of locally primitive Cayley graphs of dihedral groups which has been listed as Proposition 2.5 in this paper.

Since the order of G is 2 n p m where n 2 and p is odd, C a y ( G , S ) is not on the list of locally-primitive Cayley graphs. Thus, A 1 is not transitive on X 1 ( 1 ) . A 1 1 or 2 . | A : R ( G ) | = | A 1 | = 1 or 2, R ( G ) A . X is normal. A = R ( G ) A u t ( G , S ) .

By Proposition 3.2 and part(1) of this proof, A = R ( G ) : 2 if k 2 1 ( mod 2 n 1 p m ) , k 2 n 2 p m + 1 and gcd ( k ,2 n 1 p m ) = 1 or ( 1 k ) 2 1 ( mod 2 n 1 p m ) , k 2 n 2 p m and gcd ( 1 k ,2 n 1 p m ) = 1 .

Theorem 4.2. Suppose that S { a , a 1 , b } , then X is normal and A = G : 2 .

Proof Suppose that S { a , a 1 , b } and X = C a y ( G , S ) . Cayley graph X is also a cylinder as Figure 5. Hence A = D 2 n p m × 2 .

Theorem 4.3. Suppose that S { b , a b , a 2 n 2 p m } , then X is normal and A = G : 2 .

Proof Suppose that S { b , a b , a 2 n 2 p m } and X = C a y ( G , S ) . The Cayley graph is an Möbius ladder as Figure 6. Hence, A = D 2 n p m 2 .

Figure 5. X = C a y ( G , { a , a 1 , b } )

Figure 6. X = C a y ( G , { b , a b 1 , a 2 n 2 p m } )

Cite this paper: Kong, X. (2020) Automorphism Groups of Cubic Cayley Graphs of Dihedral Groups of Order 2npm (n ≥ 2 and p Odd Prime). Journal of Applied Mathematics and Physics, 8, 3075-3084. doi: 10.4236/jamp.2020.812226.
References

[1]   Godsil, C.D. (1981) GRRs for Nonsolvable Groups. In: Algebraic Methods in Graph Theory, Colloq. Math. Soc. Janos Bolyai, Amsterdam-New York, Vol. I, II (Szeged, 1978), 221-239.

[2]   Godsil, C.D. (1981) On the Full Automorphism Group of a Graph. Combinatorica, 1, 243-256. https://doi.org/10.1007/BF02579330

[3]   Xu, M.Y. (1998) Automorphism Groups and Isomorphisms of Cayley Digraphs. Discrete Mathematics, 182, 309-319. https://doi.org/10.1016/S0012-365X(97)00152-0

[4]   Zhou, C.X. and Feng, Y.-Q. (2007) Automorphism Groups of Connected Cubic Cayley Graphs of Order 4p. Algebra Colloquium, 14, 351-359. https://doi.org/10.1142/S100538670700034X

[5]   Xie, J.H., Yang, X. and Xu, S.J. (2019) The Normality of 3-Valent Cayley Graphs of Dihedral Groups of Order 32p. Journal of Guangxi Teachers Education University (Natural Science Edition), 36, 6-12.

[6]   Pan, J.M. (2014) Locally Primitive Cayley Graphs of Dihedral Groups. European Journal of Combinatorics, 36, 39-52. https://doi.org/10.1016/j.ejc.2013.06.041

[7]   Wang, C.Q., Wang, D.J. and Xu, M.Y. (1998) Normal Cayley Graphs of Finite Groups. Science in China (Series A), 41, 242-251. https://doi.org/10.1007/BF02879042

 
 
Top