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 is an edge of X if and only if is the edge of X. As usual, we use to denote the image of the vertex u under the permutation and 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 and . is the stabilizer of vertex in the automorphism group of X. denotes the set of vertices at distance k from vertex v. means the dihedral group of order 2n. A graph is called vertex-transitive if its automorphism group A is transitive on the vertex set . An s-arc in a graph is an ordered -tuple of vertices of the graph such that is adjacent to for and for . 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 , 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 . The Cayley graph on G with respect to S is defined to have vertex set and edge set . Let set . If , is undirected. If S is a generating system of G, 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: for some . Denote by . If S and T are equivalent, Cayley graphs and are isomorphic.
The right regular representation of group G is a subgroup of the the automorphism group A of the Cayley graph X. In particular by [1], if is the full automorphism group of X then is called a GRR (for graphical regular representation) of G. A Cayley graph is normal if is a normal subgroup of A. is transitive on G hence Cayley graph is vertex-transitive. Denote , the set of all automorphism of group G preserving S. is also a subgroup of the automorphism group of Cayley graph. In particular, is a subgroup of stabilizer of vertex identity . By [2] the normalizer of in A is the semi-direct product of and : . By [3] Proposition 1.5 X is normal if and only if . Cayley graph X is normal if and only if the automorphism group of X is . 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 where 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 be a dihedral group where and p is an odd prime number. S is an inverse-closed generating system of three elements without identity element. Then Cayley graph is GRR except the following cases:
1) where and , .
2) , .
3) , .
4) , .
2. Preliminary
Results used to prove main theorem are listed here.
Proposition 2.1. Suppose that is a dihedral group, then the automorphism group of G has the following properties.
1) Any automorphism of G can be defined as and where and .
2) where .
Proposition 2.2. Suppose G is a finite group and subsets , then .
Proposition 2.3. Let be the dihedral group of order 2n. Subsets .
Proof Let then .
The following sufficient and necessary condition of normality of Cayley graph is from paper [6].
Proposition 2.4. Let be connected. Then X is a normal Cayley graph of G if and only if the following conditions are satisfied:
1) For each there exists such that ;
2) For each , implies .
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) or ;
b) or , the incidence or non-incidence graph of the Hadamard design on 11 points;
c) or , the point-hyperplane incidence or non-incidence graph of -dimension projective geometry , where ;
d) , where d is a divisor of if (mod 4), and a divisor of if (mod 4) respectively.
2) is a normal Cayley graph and is not 2-arc-transitive, where with distinct odd primes, , and for each i. There are exactly non-isomorphism such graphs for a given order 2n.
3. Lemmas and Propositions
In the following, group G means that be dihedral group of order where and p is an odd prime number.
Proposition 3.1. If is a generating system of G of three elements, then for some .
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, where .
The proof of Proposition 3.1 will be done by the following three lemmas.
Lemma 3.1. If is a generating system of G of three elements, then S is equivalent to a subset of type for some .
Proof By proposition 2.1 in preliminary, automorphism group Aut(G) of dihedral group G is transitive on the set of involutions . One may assume that and be a generating system of G of three elements. S has three subsets of two elements: and ..
Note that, subset is a generating system of G if and only if is a generating system of G for any .
Suppose that subset ( or ) generates G. Let : , then for some . Hence .
Assume that both subset and do not generate G. Next will show that must be able to generate G.
. Hence and are mutually prime.
. Hence and are not mutually prime.
Similarly, implies that and are also not mutually prime.
, and imply that, for and , one number is power of 2 and the other one is power of p. Thus and are mutually prime.
Hence, is a generating system of G since .
Let
:
. Then
for some k.
.
Corollary 3.1. If is a generating system of G of three elements, there exists at least one subset of two elements generating G.
Lemma 3.2. If 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 where . S has three subsets of two elements: and . Next we will show that it is impossible that all three subsets of two elements generating G.
is a dihedral subgroup of G. is also a dihedral subgroup of G.
For and , one is an even number and the other one is an odd number. The orders of elements and are different: . This implies that at least one subset of and does not generate G.
Hence there are only one or two subsets of two elements of S generating G.
Lemma 3.3. Let be a generating system of G of three elements and S has two subsets of two elements generating G. If , either or .
Proposition 3.2. Suppose that is a generating system of G of three elements and .
(1) If S has only one subset of two elements generating G, then .
(2) If S has two subsets of two elements generating G, then except the following two cases. if and ; if and .
Proof (1) If there is only one subset of two elements in generating G, then , and . For any , is also a generating system of G. . Since . Hence is fixed by . .
If and then , hence .
If and , then . This implies that . Thus . This is a contradiction. For k and , one is an even number and the other one is an odd number. This implies that the orders of the element and are not equal: .
Hence .
(2) If there are two subsets of two elements of S generating G, we assume that . and .
Since subset is the only subset of two elements not generating G, for any . is fixed by . or .
If , then .
If , then . . So .
Hence if . if .
Similarly, when
,
if
.
if
.
Proposition 3.3. Suppose that S is inverse-closed generating system of three elements of G, then , or .
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 : and .
Suppose that . is also inverse-closed hence it is a set of two involutions from orbit . S generating G implies that also generates G. We get .
Suppose that S contains an involution from
.
is transitive on this orbit, we can assume that
. If
contains an involution,
by Proposition 3.1 and 2.1. If
contains no involutions,
by Proposition 2.1.
4. Results
By Proposition 3.3, we only need to discuss for and .
Firstly, we discuss .
Theorem 4.1. Suppose that is a generating system of three involutions of G and .
X is GRR except the following cases.
(1) When , and then .
(2) When , and then .
(3) If or , then .
Proof Let where and . Classify X in two cases: there are 4-cycles in X and there is no 4-cycle in X.
(1) Note that is the set of vertices at distance 2 from vertex 1.
If there are 4-cycles in X, some vertices in are coincident. Solving and we get . Solving and we get . Solving we get . Solving we get . There is no solution for other equations. Note that −1 and are two solutions of equation . 2 and are two solutions of equation . Since and we only discuss and .
(1.1) When , is a cylinder as Figure 1. Hence .
(1.2) When , X is a thickened 2-cover of the cycle graph as Figure 2. All 4-cycles in X form an imprimitive block system of A and the
Figure 1. .
Figure 2. .
kernel of the action of A on the imprimitive block system is isomorphic to . Thus .
(2) Suppose that there is no 4-cycle in X. We will count 6-cycles passing through vertex 1.
is the set of
vertices at distance 3 from vertex 1.
a) Solving and , we get . Solving and , we get . Solving and we get . Solving and we get . 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 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 . There are five 6-cycles through edge . There are three 6-cycles through edge . For any , fixes edged and hence fixes vertices set pointwise. fixes all vertices on X by the connectivity of X and the transitivity of A on . Hence . X is GRR.
b) Suppose that , , , (mod ). 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 on is faithful.
Let and fixes pointwise. Passing through vertices ,
Figure 3. .
Figure 4. .
there is a unique 6-cycle . Passing through vertices , there is a unique 6-cycle . Passing through vertices , there is a unique 6-cycle . For any , the image of a cycle of length l under is also a cycle of length l. Note that fixes pointwise, hence is also a 6-cycle passing through vertices . Hence . Follow the same argument, . So fixes all vertices on cycles . In particular, fixes pointwise. By the connectivity of X and the transitivity of A on , we get acts on faithfully.
Next, show that X is normal.
acting on faithfully implies that is isomorphic to a subgroup of symmetric group of degree 3. .
If or , then is transitive on . Since 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 where and p is odd, is not on the list of locally-primitive Cayley graphs. Thus, is not transitive on . or . or 2, . X is normal. .
By Proposition 3.2 and part(1) of this proof,
if
,
and
or
,
and
.
Theorem 4.2. Suppose that , then X is normal and .
Proof Suppose that
and
. Cayley graph X is also a cylinder as Figure 5. Hence
.
Theorem 4.3. Suppose that , then X is normal and .
Proof Suppose that
and
. The Cayley graph is an Möbius ladder as Figure 6. Hence,
.
[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