Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups

A Cayley graph X = Cay(G, S) is called normal for G if the right regular representation R(G) of G is normal in the full automorphism group Aut(X) of X. In the present paper it is proved that all connected tetravalent Cayley graphs on a minimal non-abelian group G are normal when (|G|,2) = (|G|,3) =...

Full description

Saved in:
Bibliographic Details
Published in:Algebra and Discrete Mathematics
Date:2012
Main Author: Ghasemi, M.
Format: Article
Language:English
Published: Інститут прикладної математики і механіки НАН України 2012
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/152186
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups / M. Ghasemi // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 52–58. — Бібліогр.: 14 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1860265383897858048
author Ghasemi, M.
author_facet Ghasemi, M.
citation_txt Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups / M. Ghasemi // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 52–58. — Бібліогр.: 14 назв. — англ.
collection DSpace DC
container_title Algebra and Discrete Mathematics
description A Cayley graph X = Cay(G, S) is called normal for G if the right regular representation R(G) of G is normal in the full automorphism group Aut(X) of X. In the present paper it is proved that all connected tetravalent Cayley graphs on a minimal non-abelian group G are normal when (|G|,2) = (|G|,3) = 1, and X is not isomorphic to either Cay(G, S), where |G| = 5n, and |Aut(X)| = 2m.3.5n, where m ∈ {2,3} and n ≥ 3, or Cay(G, S) where |G| = 5qn (q is prime) and |Aut(X)| = 2m.3.5.qn, where q ≥ 7, m ∈ {2,3} and n ≥ 1.
first_indexed 2025-12-07T19:00:06Z
format Article
fulltext Jo ur na l A lg eb ra D is cr et e M at h.Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 13 (2012). Number 1. pp. 52 – 58 c© Journal “Algebra and Discrete Mathematics” Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups Mohsen Ghasemi Communicated by D. Simson Abstract. A Cayley graph X=Cay(G,S) is called normal for G if the right regular representation R(G) of G is normal in the full automorphism group Aut(X) of X. In the present paper it is proved that all connected tetravalent Cayley graphs on a minimal non-abelian group G are normal when (|G|, 2) = (|G|, 3) = 1, and X is not isomorphic to either Cay(G,S), where |G| = 5n, and |Aut(X)|=2m.3.5n, where m ∈ {2, 3} and n ≥ 3, or Cay(G,S) where |G| = 5qn (q is prime) and |Aut(X)| = 2m.3.5.qn, where q ≥ 7, m ∈ {2, 3} and n ≥ 1. 1. Introduction Throughout this paper, graphs are finite and simple. For a graph X, we denote by V(X), E(X) and Aut(X) the vertex set, the edge set and the automorphism group of X, respectively, and X is said to be vertex-transitive if Aut(X) is transitive on vertices. A finite group G is called minimal non-abelian if G is not abelian, but every proper subgroup of G is abelian. For a finite group G and a subset S of G such that 1G /∈ S, and S is symmetric, that is S−1 = {s−1|s ∈ S} is equal to S. The Cayley graph X=Cay(G,S) on G with respect to S is defined as the graph with vertex set G and edge set {[g, sg]|g ∈ G, s ∈ S}. Clearly the right regular representation R(G) of G acts regularly on 2000 Mathematics Subject Classification: 05C25, 20B25. Key words and phrases: Cayley graph, normal Cayley graph, minimal non- abelian group. Jo ur na l A lg eb ra D is cr et e M at h. M. Ghasemi 53 vertices, that is, R(G) is transitive on vertices and only the identity element of R(G) fixes a vertex. Furthermore, the group Aut(G,S) ={α ∈ Aut(G)|Sα = S} is also a subgroup of Aut(X). Actually, Aut(G,S) is a subgroup of Aut(X)1, the stabilizer of the vertex 1 in Aut(X). For two groups M and N , N ⋊M denotes a semidirect product of N by M . A Cayley graph Cay(G,S) is said to be normal on G if the right reg- ular representation R(G) of G is normal in Aut(X). Let NAut(X)(R(G)) be the normalizer of R(G) in Aut(X). By Godsil [8], or Xu [14], NAut(X)(R(G))=R(G)⋊ Aut(G,S). Thus, Cay(G,S) is normal on G if and only if Aut(X)=R(G)⋊ Aut(G,S). If NAut(X)(R(G)) is transitive on edges then Cay(G,S) is called a normal edge-transitive Cayley graph by Praeger [13]. Clearly, if Cay(G,S) is normal on G and edge-transitive then it is normal edge-transitive. Note that being a normal Cayley graph is not invariant under graph isomorphism, and so strictly depends upon which group the graph is a Cayley graph on. For example, the three-dimensional hypercube Q3 ia a Cayley graph on either the group Z2 × Z2 × Z2 or the group Z4 × Z2. The Cayley graph on the first group is normal, but the Cayley graph on the second group is not. A Cayley graph X of a group G is called a graphical regular represen- tation if Aut(X)=G. It implies that Aut(X)1 = 1 and so Aut(G,S) = 1. Therefore, a necessary condition for X to be a graphical regular repre- sentation of G is Aut(G,S) = 1. In some circumstance, this necessary condition is also sufficient for X to be a graphical regular representation. However, it is of course not the case in general, that is, there exist groups G and Cayley graphs Cay(G,S) such that Aut(G,S) = 1 but Cay(G,S) is not a graphical regular representation of G. Hence the following natural problem was proposed by Godsil [9]. Problem A. Determine classes of groups G and Cayley graphs Cay(G,S) for which Cay(G,S) is a graphical regular representation of G if and only if Aut(G,S) = 1. The solution of Problem A is known only for some classes of groups. Godsil solved the problem in [8, Theorem 3.8] for p-groups with p prime which have no homomorphism onto Zp×Zp, and Li [10], solved the problem A for arbitrary cubic Cayley graphs of 2-power order, also Li and Sim solved the problem A for metacyclic p-groups with prime p (see [11]). In the present paper, it is proved that for most finite minimal non-abelian groups G, a tetravalent Cayley graph Cay(G,S) is a graphical regular representation if and only if Aut(G,S) = 1. Fang et al. [5] proved that the vast majority of connected cubic Jo ur na l A lg eb ra D is cr et e M at h. 54 Automorphism groups of tetravalent Cayley graphs Cayley graphs on non-abelian simple groups are normal. It was shown in [1, 2, 6], that most connected Cayley graphs of small valency on abelian groups are normal, and that all connected tetravalent Cayley graphs on p-groups of nilpotency class 2 with p an odd prime are normal. Also the normality of tetravalent Cayley graphs on regular p-groups was done by Feng and Xu [7]. In the present paper, we shall prove that all connected tetravalent Cayley graphs on a minimal non-abelian group are normal when (|G|, 2) = (|G|, 3) = 1, and X is not isomorphic to either Cay(G,S), where |G| = 5n, and |Aut(X)|=2m.3.5n where m ∈ {2, 3} and n ≥ 3, or Cay(G,S) where |G| = 5qn (q is prime) and |Aut(X)| = 2m.3.5.qn, where q ≥ 7, m ∈ {2, 3} and n ≥ 1. 2. Preliminaries In this section we give some results which will be used later. The following fact is basic for Cayley graphs. Proposition 2.1. [3, Lemma 16.3] A graph X is a Cayley graph of a group G if and only if Aut(X) contains a regular subgroup isomorphic to G. We have the following result for minimal non-abelian p-groups. Proposition 2.2. [12] Let G be a finite minimal non-abelian group. Then one of the following holds: (1) G is a minimal non-abelian p-group; (2) G is a semi-direct product of an elementary abelian q-group Q of order qα by a cyclic group P = 〈b〉 of order pβ, where p, q are distinct primes and the action of b on Q is an automorphism of Q of order p. Let X=Cay(G,S) be a Cayley graph on a finite group G and H a normal subgroup of G. Let XH be the quotient graph corresponding to the cosets of H in G, with two cosets adjacent in XH , whenever there is an edge between those cosets in X. Proposition 2.3 ([13]). The quotient graph XH is a Cayley graph and XH = Cay(G/H,SH/H), where SH/H = {sH|s ∈ S}. The socle of a group G is the subgroup generated by the set of all minimal normal subgroups of G, and it is denoted by soc(G). By [4, Theorem 4.3], we have the following proposition: Jo ur na l A lg eb ra D is cr et e M at h. M. Ghasemi 55 Proposition 2.4. Let G be a nontrivial finite group. Then soc(G) = T1 × ... × Tk, where Ti (1 ≤ i ≤ k) are simple normal subgroups and Ti ∼= Tj (1 ≤ i, j ≤ k). 3. Main result The main purpose of this paper is to prove the following theorem. Theorem 3.1. Let p be a prime and G a minimal non-abelian group which (|G|, 2) = (|G|, 3) = 1. Let X=Cay(G,S) be a connected tetravalent Cayley graph on G. Then we have Aut(Cay(G,S)) = R(G)⋊Aut(G,S), except when X is not isomorphic to either Cay(G,S), where |G| = 5n, and |Aut(X)|=2m.3.5n, where m ∈ {2, 3} and n ≥ 3, or Cay(G,S) where |G| = 5qn (q is prime) and |Aut(X)| = 2m.3.5.qn, where q ≥ 7, m ∈ {2, 3} and n ≥ 1. Let Q8 = 〈a, b|a4 = 1, bab−1 = a−1, a2 = b2〉, be a quaternion group, and S = {a, a3, b, b3} a subset of Q3. Now σ = (ab, a3b) ∈ A1, but σ /∈ Aut(G,S) and hence Cay(Q8, {a, a 3, b, b3}) is not normal. Also if D6 = 〈a, b|a3 = b2 = 1, b−1ab = a−1〉, and S = {a, a2, b, ab}, then δ = (a, b)(a2, ab) ∈ A1, but δ /∈ Aut(G,S) and hence Cay(D6, {a, a 2, b, ab}) is not normal. It follows that Theorem 3.1 is not true generally when (|G|, 2) 6= 1, and (|G|, 3) 6= 1. As a consequence of Theorem 3.1, we have the following result. Corollary 3.2. Let G be a minimal non-abelian group, and (|G|, 2) = (|G|, 3) = 1. Also let X is not isomorphic to either Cay(G,S), where |G| = 5n, and |Aut(X)|=2m.3.5n, where m ∈ {2, 3} and n ≥ 3, or Cay(G,S) where |G| = 5qn (q is prime) and |Aut(X)| = 2m.3.5.qn, where q ≥ 7, m ∈ {2, 3} and n ≥ 1. Then a connected Cayley graph X=Cay(G,S) of valency 4 is a graphical regular representation of G if and only if Aut(G,S) = 1. Proof of Theorem 3.1. Recall that Aut(Cay(G,S))=R(G)⋊Aut(G,S) if and only if Cay(G,S) is normal on G. Let G be a counterexample of least order, that is, G has the smallest order with the following properties: G is a minimal non-abelian group and there exists a subset S = {s1, s2, s −1 1 , s−1 2 } of G such that X=Cay(G,S) is not a normal 4-valent connected Cayley graph. Let A=Aut(X) and let A1 be the stabilizer of 1 in A. Since X has valency 4, the stabilizer A1 of the vertex 1 in A is a {2, 3}-group. By Proposition 2.2, first assume that G is a p-group. By our assumption G is not 2- or 3-group. By Proposition 2.4, soc(A) = T1 × ... × Tk, where Jo ur na l A lg eb ra D is cr et e M at h. 56 Automorphism groups of tetravalent Cayley graphs k ≥ 1 and Ti ∼= Tj (1 ≤ i, j ≤ k). T is a {2, 3, p}-group because A is {2, 3, p}-group. First let T be an abelian group. Then soc(A) is an elementary abelian q-group, where q = 2, 3, or p. If H =soc(A) is transitive on V(X), then H =soc(A) acts regularly on V(X). Thus |soc(A)| = |G|, and hence soc(A) = G, a contradiction. So H =soc(A) is not transitive on V(X). Now assume that Σ = {B1, B2, ..., Bt} is the set of orbits of H on V(X). By the normality of H in A we have that t and |Bi| (1 ≤ i ≤ t) are powers of p. It follows that H is a p-group and H ≤ G. Consider the quotient graph XH defined by V(XH)=Σ, and (Bi, Bj) ∈ E(XH) if and only if there exists vi ∈ Bi, vj ∈ Bj such that (vi, vj) ∈ E(X). Since the quotient group G/H acts regularly on Σ, therefore by Proposition 2.1 XH must be connected Cayley graph of G/H. So by Proposition 2.3 XH ∼= Cay(G,S), where G = G/H and S = {sH|s ∈ S}. Since |V (XH)| is odd, the valency v(XH) of XH could not be 3 and hence v(XH) = 2, or v(XH) = 4. If v(XH) = 4 and G/H be a non-abelian, then by the minimality of |G|, XH is normal as a Cayley graph of G/H. Thus G/HEAut(XH). Let K be the kernel of A on Σ. Also let K1 be the stabilizer of the vertex 1 in K. Then K1 fixes the neighborhood N(1) of 1 in X pointwise. Since X is connected, K1 fixes each vertex in X. Thus K1 = 1, and hence K = H. Therefore A/H≤ Aut(XH), and G/H is normal in A/H, which implies that GE Aut(X), a contradiction. Now if v(XH)=4 and G/H is an abelian, then by [2], XH is normal except when XH=Cay(G/H,SH/H), where G/H ∼= Z5. If XH is normal, then G/HEAut(XH) and so GE Aut(X), a contradiction. Now suppose that XH = K5, and Aut(XH)=S5. Therefore |A/H| | 23.3.5 and hence |Aut(X)|=2m.3.5n, where m ∈ {2, 3} and n ≥ 3. If 3 ∤ |A|, then clearly R(G) E A, a contradiction. Thus 3 | |A|. Now X=Cay(G,S) is not normal. Suppose to the contrary that X is normal. Hence A1=Aut(G,S), and so 3 | |Aut(G,S)|. Therefore there exists an element α of order 3 in Aut(G,S). Then |S| = 4 implies that α fixes an element in S, say s. Consequently, α fixes s−1. Since s, s−1 ∈ S and s 6= s−1, we have that α fixes S pointwise and hence 〈S〉 = G implies α = 1, a contradiction. Now assume that v(XH) = 2. Then XH is a cycle of length pm =| G/H |, for some positive integer m. Also Aut(XH)∼= D2pm . We have SH/H = {Hs1, Hs2}. Clearly Hs1 6= Hs−1 1 and Hs2 6= Hs−1 2 . Therefore Hs1 = Hs−1 2 , and s1s2 ∈ H. If H ∩ S 6= ∅, then G = H, a contradiction. So H ∩ S = ∅, and hence G = 〈H, s1〉. Now since G/H is a cyclic group and {Hs1} is a minimal generating set, by [14, Proposition 3.1], we have Aut(X)=G/H, a contradiction. Now let T is not an abelian group. Assume that H=soc(A)∩G. By Jo ur na l A lg eb ra D is cr et e M at h. M. Ghasemi 57 considering the order of A, one has H 6= 1. Clearly H is not transitive on V (X). Now assume that Σ = {B1, B2, ..., Bs} is the set of orbits of H on V(X). By the normality of H in G we have that s and |Bi| (1 ≤ i ≤ s) are powers of p. Considering the quotient graph XH defined by V(XH)=Σ, and (Bi, Bj) ∈ E(XH) if and only if there exists vi ∈ Bi, vj ∈ Bj such that (vi, vj) ∈ E(X). Since the quotient group G/H acts regularly on Σ, therefore XH must be connected Cayley graph of G/H. So XH ∼= Cay(G,S), where G = G/H and S = {sH|s ∈ S}. Now with the same arguments as before we get same result. Finally assume that G = Q⋊P , where P and Q are Sylow p-subgroup and Sylow q-subgroup of G, respectively such that P is a cyclic group and Q ∼= Zq × Zq × ... × Zq. Now considering soc(A) = T1 × ... × Tk, where k ≥ 1 and Ti ∼= Tj (1 ≤ i, j ≤ k). If soc(A) is {2, 3}-group, Then Soc(A) is abelian 2-group or abelian 3-group. Clearly Soc(A) is not transitive on V(X). Now assume that Σ = {B1, B2, ..., Bs} is the set of orbits of soc(A) on V(X). By the normality of soc(A) in A, p, q or pq divides s and |Bi| (1 ≤ i ≤ s). This is a contradiction. Thus H=soc(A)∩G 6= 1 and H is not transitive on V (X). Now assume that Σ = {B1, B2, ..., Bs} is the set of orbits of H on V(X). By the normality of H in G, p, q, or pq divides s and |Bi| (1 ≤ i ≤ s). Since the quotient group G/H acts regularly on Σ, therefore XH must be connected Cayley graph of G/H. So XH ∼= Cay(G,S), where G = G/H and S = {sH|s ∈ S}. Since |V (XH)| is odd, the valency v(XH) of XH could not be 3 and hence v(XH) = 2, or v(XH) = 4. If v(XH) = 4 and G/H be a non-abelian, then by the minimality of |G|, XH is normal as a Cayley graph of G/H. Thus G/HEAut(XH). Let K be the kernel of A on Σ. Also let K1 be the stabilizer of the vertex 1 in K. Then K1 fixes the neighborhood N(1) of 1 in X pointwise. Since X is connected, K1 fixes each vertex in X. Thus K1 = 1, and hence K = H. Therefore A/H≤ Aut(XH), and G/H is normal in A/H, which implies that GE Aut(X), a contradiction. Now if v(XH)=4 and G/H is an abelian, then by [2], XH is normal except when XH=Cay(G/H,SH/H), where G/H ∼= Z5. If XH is normal, then G/HEAut(XH) and so GE Aut(X), a contradiction. Now suppose that XH = K5, and Aut(XH)=S5. Therefore |Aut(X)|=2m.3.5.qn, where m ∈ {2, 3} and n ≥ 1. If 3 ∤ |A|, then |A| = 2m.5.qn. Clearly PQ/QEA/Q and so PQ E A. Thus R(G) E A, a contradiction. Thus 3 | |A|. Now X=Cay(G,S) is not normal. Suppose to the contrary that X is normal. Hence A1=Aut(G,S), and so 3 | |Aut(G,S)|. Therefore there exists an element α of order 3 in Aut(G,S). Then |S| = 4 implies that α fixes an element in S, say s. Consequently, α fixes s−1. Since s, s−1 ∈ S and Jo ur na l A lg eb ra D is cr et e M at h. 58 Automorphism groups of tetravalent Cayley graphs s 6= s−1, we have that α fixes S pointwise and hence 〈S〉 = G implies α = 1, a contradiction. Now assume that v(XH) = 2. Then XH is a cycle of length pmqn =| G/H |, for some positive integer m, n. Also Aut(XH)∼= D2pmqn . We have SH/H = {Hs1, Hs2}. Clearly Hs1 6= Hs−1 1 and Hs2 6= Hs−1 2 . Therefore Hs1 = Hs−1 2 , and s1s2 ∈ H. If H ∩ S 6= ∅, then G = H , a contradiction. So H ∩ S = ∅, and hence G = 〈H, s1〉. Now since G/H is a cyclic group and {Hs1} is a minimal generating set, by [14, Proposition 3.1], we have Aut(X)=G/H, a contradiction. References [1] Y. G. Baik, Y. Q. Feng, and H. S. Sim, The normality of Cayley graphs of finite Abelian groups with valency 5, Systems Sci. Math. Sci. 13 (2000) 425-431. [2] Y. G. Baik, Y. Q. Feng, H. S. Sim, and M. Y. Xu, On the normality of Cayley graphs of Abelian groups, Algebra Colloq. 5 (1998) 297-304. [3] N. Bigss, Algebraic Graph Theory, second ed., Cambridge University Press, Cam- bridge, 1993. [4] J. D. Dixon, and B. Mortimer, Permutation Groups (Springer, New York, 1996). [5] X. G. Fang, C. H. Li, J. Wang, and M. Y. Xu, On cubic Cayley graphs of finite simple groups, Discrete Math. 244 (2002) 67-75. [6] Y. Q. Feng, J. H. Kwak, and R. J. Wang, Automorphism groups of 4-valent connected Cayley graphs of p-groups, Chinese Ann. Math. 22 B (2001) 281-286. [7] Y. Q. Feng, and M. Y. Xu, Automorphism groups of tetravalent Cayley graphs on regular p-groups, Discrete Math. 305 (2005) 345-360 [8] C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981) 243-256. [9] C. D. Godsil, The automorphism group of some cubic Cayley graphs, Europ. J. Combin. 4 (1983), 25-32. [10] C. H. Li, The solution of a problem of Godsil on cubic Cayley graphs, J. Combin. Theory Ser. B 72 (1998), 140-142. [11] C. H. Li, and H. S. Sim, The graphical regular representations of metacyclic p-groups, Europ. J. Combin. 21 (2000), 917-925. [12] G. A. Miller, and H. C. Moreno, Non-abelian groups in which every subgroup is abelian, Trans. Amer. Math. Soc. 4 (1903), 398-404. [13] C. E. Preager, Finite normal edge-transitive Cayley graphs, Bull. Austral. Math. Soc. 60 (1999), 207-220. [14] M. Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309-319. Contact information M. Ghasemi Department of Mathematics, Urmia University, Urmia 57135, Iran E-Mail: m.ghasemi@urmia.ac.ir Received by the editors: 13.10.2011 and in final form 27.11.2011. M. Ghasemi
id nasplib_isofts_kiev_ua-123456789-152186
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1726-3255
language English
last_indexed 2025-12-07T19:00:06Z
publishDate 2012
publisher Інститут прикладної математики і механіки НАН України
record_format dspace
spelling Ghasemi, M.
2019-06-08T09:48:59Z
2019-06-08T09:48:59Z
2012
Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups / M. Ghasemi // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 52–58. — Бібліогр.: 14 назв. — англ.
1726-3255
2000 Mathematics Subject Classification:05C25, 20B25.
https://nasplib.isofts.kiev.ua/handle/123456789/152186
A Cayley graph X = Cay(G, S) is called normal for G if the right regular representation R(G) of G is normal in the full automorphism group Aut(X) of X. In the present paper it is proved that all connected tetravalent Cayley graphs on a minimal non-abelian group G are normal when (|G|,2) = (|G|,3) = 1, and X is not isomorphic to either Cay(G, S), where |G| = 5n, and |Aut(X)| = 2m.3.5n, where m ∈ {2,3} and n ≥ 3, or Cay(G, S) where |G| = 5qn (q is prime) and |Aut(X)| = 2m.3.5.qn, where q ≥ 7, m ∈ {2,3} and n ≥ 1.
en
Інститут прикладної математики і механіки НАН України
Algebra and Discrete Mathematics
Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups
Article
published earlier
spellingShingle Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups
Ghasemi, M.
title Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups
title_full Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups
title_fullStr Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups
title_full_unstemmed Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups
title_short Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups
title_sort automorphism groups of tetravalent cayley graphs on minimal non-abelian groups
url https://nasplib.isofts.kiev.ua/handle/123456789/152186
work_keys_str_mv AT ghasemim automorphismgroupsoftetravalentcayleygraphsonminimalnonabeliangroups