ABSTRACT

A graph G is called $\left(X,s\right)$ -arc regular, if $X\le Aut\Gamma$ is regular on s-arc set. Feng’s paper [1] determined all one-regular graphs of square-free order and prime valent are Cayley graphs. Quite a lot of works with small valency are known, see [2] [3] [4] . We determined all 2-arc-regular graphs of square-free order and prime valency, where the degree $t\equiv 3\left(mod4\right)$ .

Keywords:Automorphism Group, Arc-Regular Graph, Cayley Graph

平方自由阶素数度2-弧正则图

丁梦琳

云南财经大学统计与数学学院，云南 昆明

收稿日期：2018年4月8日；录用日期：2018年4月20日；发布日期：2018年4月27日

摘 要

称一个图为s-弧正则图，如果图的全自同构群在图的s弧集上是正则的。Feng等在 [1] 中证明了素数度的1-弧正则图都是Cayley图，随后出现一些小度数图的研究，见 [2] [3] [4] 。本文即确定了平方自由阶素数度的2-弧正则图，其中度数t满足 $t\equiv 3\left(mod4\right)$ 。

关键词 :自同构群，弧正则图，凯莱图

Copyright © 2018 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

一个图与其全自同构群密切相关，全自同构群是图论中的一个基本且重要的研究对象，一个图的全自同构群越大，图的对称性越好，故寻找一个图的自同构群便成为研究图的首要却也十分困难的任务。正则图是一类简单图，图的许多性质都是从正则图的研究开始的，比如正则图的连通性，对称性，所以研究正则图的性质成为图论的一个活动领域。本文便完全确定了平方自由阶的素数度2-弧正则图，其中度 $t\equiv 3\left(\mathrm{mod}4\right)$ 。

本文所得主要结果如下：

定理1.1. 设G为2n阶t度的2-弧正则图，其中n为平方自由的且至少包含三个素因子，t素数，且 $t\equiv 3\left(\mathrm{mod}4\right)$ ，则 $t=3$ ，且G满足：

$Aut\Gamma =PSL\left(2,q\right)$ ， ${\left(Aut\Gamma \right)}_{\alpha }=S_3$ ，其中 $q\equiv \pm 3\left(\mathrm{mod}8\right)$ ， $n=\frac{q\left(q+1\right)\left(q-1\right)}{24}.$

2. 预备引理

为了证明以上定理，我们给出几个重要的结果。

首先是含有二面体Sylow 2-子群的有限群，参见[ [5] ，引理2.4]。

引理2.1. 设G为一个含二面体Sylow 2-子群的有限群，M是G的最大奇数阶正规子群，则G/M同构于下列群之一：

1) (二面体) 2-子群；

2) $A_4$ 或 $A_7$ ；

3) $Aut\left(PSL\left(2,q\right)\right)$ 的包含 $PSL\left(2,q\right)$ 的子群，其中 $q\ge 5$ 为奇素数幂。

下面给出关于局部本原图的一个性质。参见[ [6] ，定理4]。

引理2.2. 设 $\Gamma =\left(V,E\right)$ 为平方自由阶k度， $k\ge 3$ 的G-局部本原联通图。假设G在VG上传递且G不是完全二部图，则下述之一成立：

1)，2nk为平方自由的，k为nk的最小素因子，G为二面体 $D_{2n}$ 上的Cayley图；

2) $G=M:X$ ，其中M为平方自由阶的，X为几乎单群且

a) $soc\left(G\right)=M_{11},M_{12},M_{22},M_{23},M_{24,}{J}_1$ ；

b) $G=A_n$ 或者 $S_n$ ，其中 $n<3k$ ；

c) $G=PSL\left(2,p\right)$ 或 $G=PGL\left(2,p\right)$ ；

d) $soc\left(G\right)=PSL\left(2,p^f\right)$ ， $f\ge 2$ ，且 $p^f>9$ ，或者 $k|p^{f-1}$ 或者 $f=2$ ， $k|p+1$ ；

e) G为Lie型单群 $GF\left(p^f\right)$ ， $p\le k$ ，或者 $\left[\frac{d}{2}\right]f<k$ ，G为d维典型群， $d\ge 3$ 。或者 $2f<k$ ，

$soc\left(G\right)=G_2\left(p^f\right),D_4\left(p^f\right),F_4\left(p^f\right),E_6\left(p^f\right),E_7\left(p^f\right)$ 。且 $MT=M\times T$ 有至多两个轨道并且G为T-边传递图，特别地，如 $T=PSL\left(2,p\right)$ ，则 $M,T_{\alpha },k$ 满足[ [6] ，表3]。

下面给出平方自由阶弧传递3度图的一个引理，参见 [7] 。

引理2.3. 设G为2n阶弧传递3度图，其中n为平方自由的且至少包含三个素因子，则下述之一成立：

1) $Aut\left(\Gamma \right)$ 可解，且 $Aut\left(\Gamma \right)\cong D_{2n}:Z_3$ ；

2) $Aut\left(\Gamma \right)=PSL\left(2,p\right)$ ，其中 $p\ge 19$ 为一素数。

下面的定理稍微改进了Praeger，参见[ [8] ，定理4.1]的一个著名结果，见 [9] 。

命题2.1. 设G为素数度 $\left(X,s\right)$ -弧正则图，且假设 $N⊲X\le Aut\Gamma$ 在VG上至少有3个轨道，则下述之一成立：

1) N在VG半正则， $X/N\le Aut\left({\Gamma }_N\right)$ 为 $\left(X/N,s\right)$ -弧正则图，且G为 ${\Gamma }_N$ 的一个正规N-覆盖；

2) $X_{\alpha }\cong {\left(X/N\right)}_{\delta }$ ，其中 $\alpha \in V\Gamma$ ， $\delta \in V{\Gamma }_M$ ；

3) 如果X有一正规子群 $M\subset N$ ，则 ${\Gamma }_M$ 为 $\left(X/M,s\right)$ -弧正则，且是 ${\Gamma }_N$ 的一个正规N/M-覆盖。

群 $PSL\left(2,q\right)$ 的极大子群是知道的，下面我们给出一个引理，参见 [10] 。

引理2.4. 设 $G=PSL\left(2,q\right)$ ， $q=p^n\ge 5$ ，p为素数，则G的极大子群同构于下列群之一：

1) $D_{\frac{2\left(q-1\right)}{d}}$ ，其中 $d=\left(2,q-1\right)$ ，且 $q\ne 5,7,9,11$ ；

2) $D_{\frac{2\left(q+1\right)}{d}}$ ，其中 $$ ，且 $q\ne 7,9$ ；

3)

4) $A_4$ ，其中 $q=p=5$ ，或 $q=p=3,13,27,37\left(\mathrm{mod}40\right)$ ；

5) $S_4$ ，其中 $q\equiv \pm 1\left(\mathrm{mod}8\right)$ ；

6) $A_5$ ，其中 $q\equiv \pm 1\left(\mathrm{mod}10\right)$ ；

7) $PSL\left(2,p^m\right)$ ， $n/m$ 为奇素数；

8) $PSL\left(2,p^{\frac{n}{2}}\right)$ ，n为偶数。

接下来我们给出 $PSL\left(2,q\right)$ 极大子群 [10] 的一个推论。

推论2.1. 设 $H\cong Z_t:Z_{t-1}$ 为 $PSL\left(2,q\right)$ 的子群，其中 $q\ge 5$ ，t都是奇素数。则 $t=3$ 。

证明：因为q为奇素数， $d=\left(2,q-1\right)=2$ ，H包含在 $PSL\left(2,q\right)$ 的极大子群里，我们逐一验证引理2.4的可能的情况。(1)~(3)由阶数算是不可能的，排除。(7)和(8)中，因为q为奇素数，没有p值使之存在,排除。(4)和(5)中，H为 $Z_3:Z_2$ 满足。(6)中， $A_5$ 中没有20阶的子群，排除。综上，H只可能为 $Z_3:Z_2$ ，我们得到 $t=3$ 。

通过Magma [8] ，我们可以检验一个图是否为3度2-弧正则图。我们给出一个2-弧正则图关于 $PSL\left(2,19\right)$ 的例子。

例子2.1. 设 $G=PSL\left(2,19\right)$ 为作用在20个点上的置换群。设：

a = (1, 3)(2, 13)(4, 5)(6, 10)(7, 12)(8, 19)(9, 14)(11, 15)(16, 17)(18, 20)；

b = (1, 16, 4)(3, 5, 17)(6, 20, 7)(8, 15, 9)(10, 12, 18)(11, 19, 14)；

c = (1, 18)(2, 8)(3, 20)(4, 16)(5, 17)(6, 11)(7, 9)(10, 15)(12, 14)(13, 19)；

证明：设 $H=\langle a,b\rangle$ ，则 $H\cong S_3$ ， $\langle H,c\rangle =G$ 且 $\left|H:H\cap H^c\right|=3$ ，因此 $\mathrm{Cos}\left(G,H,HcH\right)$ 是 $\left(G,2\right)$ -弧正则3度图。而且这个图是在同构意义下的自同构群为 $PSL\left(2,19\right)$ 的2-弧正则3度图。

接下来给出一个2-弧正则图关于 $PSL\left(2,29\right)$ 的例子。

例子2.2. 设 $G=PSL\left(2,29\right)$ 为作用在30个点上的置换群。设

e = (3, 16)(4, 20)(5, 26)(6, 9)(7, 28)(8, 14)(10, 18)(11, 12)(13, 29)(15, 23)(17, 30)(19, 25)(21, 22)(24, 27)；

f = (1, 14, 8)(2, 7, 28)(3, 27, 10)(4, 9, 13)(5, 12, 21)(6, 20, 29)(11, 26, 22)(15, 30, 19)(16, 18, 24)(17, 23, 25)；

g₁ = (1, 2)(3, 25)(4, 7)(5, 29)(6, 15)(8, 17)(9, 23)(10, 27)(13, 26)(14, 30)(16, 19)(18, 24)(20, 28)(21, 22)；

g₂ = (1, 2)(4, 21)(5, 11)(6, 25)(7, 23)(8, 14)(9, 19)(10, 30)(12, 26)(13, 24)(15, 28)(17, 18)(20, 22)(27, 29)。

证明：设 $H=\langle e,f\rangle$ 用Magma计算可知： $H\cong S_3$ ， $\langle H,g_1\rangle =\langle H,g_2\rangle =G.$

$\left|H:H\cap H^{g_1}\right|=\left|H:H\cap H^{g_2}\right|=3$ ，因此 $\mathrm{Cos}\left(G,H,H{g}_{1}H\right)$ 和 $\mathrm{Cos}\left(G,H,H{g}_{2}H\right)$ 是 $\left(G,2\right)$ -弧正则3度图。更多的，这两个图是同构意义下，以 $PSL\left(2,29\right)$ 作为全自同构群的唯一的两个不同构的2-弧正则3度图。

3. 定理证明

设G为2n阶素数度t度的2-弧正则图，其中 $n=p_1{p}_2\cdots p_s$ ， $s\ge 3$ ， $p_i$ ， $1\le i\le s$ 为不同的素数。设 $\alpha \in V\Gamma$ ， $A=Aut\Gamma$ 表示图G的全自同构群。

定理3.1. 假设A可解，则图G不存在。

证明：如果图G存在，首先假设G是完全二部图，则 $\Gamma =K_{t,t}$ ，当 $t\ge 5$ 时， $Aut\Gamma \cong \left(S_t\times S_t\right):Z_2$ 是不可解的，与A可解矛盾。当 $t=3$ 时， $Aut\Gamma \cong \left(S_3\times S_3\right):Z_2$ 且G是3度图，此时 $\left|V\Gamma \right|=6$ ， $\left|A\right|=\left|A_{\alpha }\right|\times \left|V\Gamma \right|$ ，则 $\left|A_{\alpha }\right|=12$ ，而3度2-弧正则图的点稳定子群阶为6，矛盾。

假设G不是完全二部图，因为素数度的图一定是局部本原图，所以G满足引理2.2，又因为A是可解的，所以G满足引理2.2 (1)，于是 $A=D_{2n}:Z_k$ ， $\left|A\right|=2nt$ ，则 $\left|A_{\alpha }\right|=t$ 与图G为2-弧正则图矛盾。综上，图G不存在，定理得证。

下面我们给出定理1.1的证明。

定理3.2. 设 $t\equiv 3\left(\mathrm{mod}4\right)$ ，A不可解，则图G满足定理3.1。

证明：因为G为t度的2-弧正则图，所以 $\left|A\right|=2nt\left(t-1\right)$ ， $t\equiv 3\left(\mathrm{mod}4\right)$ ，设A的Sylow 2-子群 $A_2$ ，则 $A_2\cong Z_4$ 或 $Z_2^2$ 。

如果 $A_2\cong Z_4$ 为循环群，因为Sylow 2-子群是循环群的有限群都是可解的，所以推出矛盾。于是 $A_2\cong Z_2^2$ ，A满足引理2.1。设M为A的最大的奇数阶正规子群，逐一分析A/M的可能性，如果A/M为可解的，则由M为可解群，可推出A可解，矛盾。于是 $A/M\cong A_7$ 或满足引理2.1 (3)。如果 $A/M\cong A_7$ ，则 ${\left|A/M\right|}_2=8$ ，这与 ${\left|A/M\right|}_2=4$ 矛盾。所以 $PSL\left(2,q\right)\le A/M\le Aut\left(PSL\left(2,q\right)\right)=PGL\left(2,q\right)\cdot Z_f=PSL\left(2,q\right)\cdot Z_2\cdot Z_f$ ，其中 $q=p^f$ ，p为素数。

断言： $A=M\cdot PSL\left(2,q\right)$ 且 $f=1$ 。

假设 $A/M\ne PSL\left(2,q\right)$ ，因为 ${\left|PSL\left(2,q\right)\right|}_2=4={\left|A\right|}_2$ ，所以 $A/M\ne PSL\left(2,q\right)$ $Z_2=PGL\left(2,q\right)$ ，所以 $f>2$ 且f不是2的方幂。因为G为2-弧正则图，由引理3.1中类似的分析，可知G不是完全二部图。由假设，A不可解，所以G满足引理2.2 (2)部分。

于是可以设 $A=N:X$ ，N是平方自由阶的，X为几乎单群， $soc\left(X\right)=T$ 。

考虑到 $PSL\left(2,q\right)\le A/M\le Aut\left(PSL\left(2,q\right)\right)$ ，可推出 $M=N$ 且 $T=PSL\left(2,q\right)$ 。下面逐一验证引理2.2 (2) (i)-(v)。

因为 $T=PSL\left(2,q\right)$ ，所以(i)和(ii)直接可排除；假设满足(iii)，则 $M=1$ 且 $A=A/M=PSL\left(2,q\right)$ 或 $A=A/M=PGL\left(2,q\right)$ ，均与假设矛盾。假设满足(iv)，则 $T=PSL\left(2,p^f\right)$ ， $f\ge 2$ 且 $p^f>9$ ， $t|p^{f-1}$ 。因为 $f>2$ ，所以 $p^2|\left|A\right|=2nt\left(t-1\right)$ ，如果 $t=p$ ，则 $p|n$ 且 $f=2$ ，矛盾。如果 $t\ne p$ ，则 $p^2|\left(t-1\right)$ 或，且 $p|t-1$ ，总之， $p|t-1$ ，所以 $\left(p,t\right)=1$ ，这与 $p|p^{f-1}$ 矛盾。 $f=2$ 与假设矛盾。假设满足(iv)，如果A为d维典型群，此时 $d\ge 3$ ，矛盾。如果 $soc\left(A\right)=G_2\left(p^f\right),D_4\left(p^f\right),F_4\left(p^f\right),E_6\left(p^f\right),E_7\left(p^f\right)$ ，则与 $T=PSL\left(2,q\right)$ 矛盾。

于是断言成立。

假设M在VG上传递，则 $\left|{\alpha }^M\right|=\left|V\Gamma \right|=\left|M:M_{\alpha }\right|=2n$ 为偶数，这与 $\left|M\right|$ 是奇数矛盾。

假设M在VG上有两个轨道，记为 ${\Delta }_1$ ， ${\Delta }_2$ ，设 $A^{+}=A_{{\Delta }_1}=A_{{\Delta }_2}$ ，由 [9] ，之所以 $A_{{\Delta }_1}=A_{{\Delta }_2}$ ，是因为 $A_{{\Delta }_1}=\left\{g\in A|{\Delta }_1^g={\Delta }_1\right\}$ ， $A_{{\Delta }_2}=\left\{m\in A|{\Delta }_2^g={\Delta }_2\right\}$ ，下证 ${\Delta }_2^g={\Delta }_2$ ，因为 ${\Delta }_1$ ， ${\Delta }_2$ 为block，故如果不成立，则满足 ${\Delta }_2^g={\Delta }_1,{\Delta }_1^{g^{-1}}={\Delta }_2$ 。

( ${\left({\Delta }_1^g\right)}^{g^{-1}}={\Delta }_2={\Delta }_1$ ，矛盾。)而且，因为A在VG上传递，所以 $\left|A:A^{+}\right|=2$ 。由Frattini论断， $A^{+}=M{A}_{\alpha }{}^{+}=M{A}_{\alpha }$ ，则 $A^{+}/M=M{A}_{\alpha }/M\cong A_{\alpha }/A_{\alpha }\cap M$ 为可解的，且M可解，故 $A^{+}$ 可解。又因为 $\left|A:A^{+}\right|=2$ ， $A^{+}⊲A$ ，故A可解。矛盾。

假设M在VG上至少有三个轨道，由命题2.1，由M诱导的正规商图 ${\Gamma }_M$ 为 $\left(A/M,2\right)$ -弧正则图，其

中 $\left|V{\Gamma }_M\right|=\frac{2n}{\left|M\right|}$ 为平方自由的，。设 $\alpha \in V\Gamma$ ， $\delta \in V{\Gamma }_M$ ， $\bar{A}=A/M$ ，则

$A_{\alpha }\cong {\bar{A}}_{\alpha }\cong {\mathbb{Z}}_t:{\mathbb{Z}}_{t-1}$ 。设 $\overline{A_{\sigma }}\le Y$ ，Y为 $PSL\left(2,q\right)$ 的极大子群，由断言，我们知道q为奇素数，所以由推论得 $t=3$ 。最后，因为A不可解且 ${\left|A\right|}_2=4$ ，由引理2.3，我们得到 $\left(A,A_{\alpha }\right)=\left(PSL\left(2,q\right),S_3\right)$ ，且 $q\ge 19$ 为奇素数。因为 $\left|A:A_{\alpha }\right|=\frac{q\left(q-1\right)\left(q+1\right)}{24}=2n$ ，其中n是平方自由的奇素数，所以 $8|q^2-1$ ， $16\nmid q^2-1$ ， $8\nmid q+1$

且 $8\nmid q-1$ ，得 $q\equiv \pm 3\left(\mathrm{mod}8\right)$ 且 $n=\frac{q\left(q+1\right)\left(q-1\right)}{24}$ 定理得证。

问题：虽然本文已得到一些较好的结果，但还是有许多的不足之处，例如：没有得到对于 $s\ge 2$ 时的平方自由阶s-弧正则图的一般结论。这将是一个巨大的工作。

文章引用

丁梦琳. 平方自由阶素数度2-弧正则图
2-Arc-Regular Graphs of Square-Free Order and Prime Valency[J]. 应用数学进展, 2018, 07(04): 369-373. https://doi.org/10.12677/AAM.2018.74046

参考文献