DOI:10.12677/AAM.2018.74046,PDF,HTML,XML,被引量下载: 1,451浏览: 3,690
作者:丁梦琳：云南财经大学统计与数学学院，云南 昆明
关键词:自同构群；弧正则图；凯莱图；Automorphism Group；Arc-Regular Graph；Cayley Graph

文章引用：丁梦琳. 平方自由阶素数度2-弧正则图[J]. 应用数学进展, 2018, 7(4): 369-373. https://doi.org/10.12677/AAM.2018.74046

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-弧正则图的一般结论。这将是一个巨大的工作。

参考文献

[1]	Feng, Y.Q. and Li, Y.T. (2011) One-Regular Graphs of Square-Free Order of Prime Valency. European Journal of Combinatorics, 32, 261-275. https://doi.org/10.1016/j.ejc.2010.10.002
[2]	Fang, X., Wang, J. and Xu, M.Y. (2002) On 1-Arc-Regular Graphs. European Journal of Combinatorics, 23, 785-791. https://doi.org/10.1006/eujc.2002.0579
[3]	Feng, Y.Q. and Kwak, J.H. (2004) One-Regular Cubic Graphs of Order a Small Number Times a Prime or Prime Square. Journal of the Australian Mathematical Society, 76, 345-356. https://doi.org/10.1017/S1446788700009903
[4]	Feng, Y.Q. and Kwak, J.H. (2007) Cubic Symmetric Graphs of Order a Small Number Times a Prime or a Prime Square. Journal of Combinatorial Theory, Series B, 97, 627-646. https://doi.org/10.1016/j.jctb.2006.11.001
[5]	Pan, J.M., Ding, S.Y. and Liu, Y. (2014) Finite Arc-Regular Graphs of Prime Valency. Scientia Sinica Mathematica, 44, 307-315. https://doi.org/10.1360/012014-1
[6]	Li, C.H., Lu, Z.P. and Wang, C.X. (2015) On Edge-Transitive Graphs of Square-Free Order. European Journal of Combinatorics, 22, 41-46. https://doi.org/10.1016/j.ejc.2014.10.005
[7]	Ling, B. and Lou, B.G. (2017) Arc-Transitive Cubic Graphs of Order Four Times an Odd Square-Free Integer. Journal of Algebra and Its Applications, 16, 213-225. https://doi.org/10.1142/S0219498817502139
[8]	Bosma, W., Cannon, J. and Playoust, C. (1997) The MAGMA Algebra System I: The User Language. Journal of Symbolic Computation, 24, 235-265. https://doi.org/10.1006/jsco.1996.0125
[9]	Biggs, N. (1992) Algebraic Graph Theory. 2nd Edition, Cambridge University Press, New York.
[10]	Dickson, L.E. (1958) Linear Groups with an Expositions of the Galois Field Theory. Dover.