1. 引言
本文中研究的图都是有限的,连通的,无向的,无重边的,无自环的。此外,图是由顶点集和顶点间的邻接关系构成的。对于一个图
,它的每条边都可以看作方向相反的两条弧。用
,
,
,
分别表示图
的顶点集合,边集合,弧集合和图的全自同构群。如果
在
,
或
上的作用传递,则分别称图为点传递,边传递或弧传递。此外,弧传递图也称为对称图。设
为正整数,
为图,图
的一个s-弧是指图
中的
个有序点列
,并且满足
,且
和
是邻接的。如果图
的自同构群
在
的s-弧集上传递,则称
是
-弧传递图;如果
是
-弧传递图,但不是
-弧传递图,则称
为
-传递图。特别地,0-弧传递就是点传递,1-弧传递就是弧传递(或对称)。
代数图论作为图论的重要分支之一,其主要应用代数的方法来解决一些图论问题,它在计算机科学技术的并行处理、编码等领域有着广泛的应用(参看文献 [1] [2] [3] ),因此,从理论上研究一些图的相关性质及其分类等具有十分重要的意义。此外,在代数图论中,国内外的学者们对于阶数固定的对称图关注颇多并且引起了它们很大的兴趣。在许多文献中,人们把大量的注意力放在描述一个阶数很小的素数幂的边传递或弧传递图上。这是因为这些图不仅可以提供一些有趣图的丰富来源,而且(可能更重要的是)刻画研究更大的传递图。例如:设p,q是两个不同的素数,在文献( [4] )中,Chao分类了阶为p的对称图;Cheng和Oxley在( [5] )中分类了阶为2p的对称图;Wang和Xu在文献( [6] )中确定了所有阶为3p的对称图。之后,Praeger等在( [7] [8] )中将这些结果推广到阶为pq的对称图。文献( [9] [10] [11] )分类了阶为2p2的4度图和5度图。此外,Feng等在文献( [12] )确定了阶为2pq的5度对称图;在文献( [13] )中Pan等分析了2p2阶的5度对称图及其正规覆盖。
一般情况下,我们研究对称图的一个典型的方法就是作正规商图,其定义如下:设
为G-弧传递图,且G有一个在
上不传递的正规子群N,定义图
的由N诱导出的正规商图(记为
)的顶点集为
上的所有轨道(记为
),且
的两个顶点
邻接当且仅当B中的某个顶点与C中的某个顶点在
中邻接。特别地,如果
和
的度数相同,则称
为
的正规覆盖。基于这个定义,我们研究对称图一般需要研究分析对称图的基图及其正规覆盖。
基图的分类不仅对分析对称图是一个基础,也是研究基图覆盖的重要手段。而且研究阶数为素数幂的小倍数的对称图是代数图论中重要且热门的话题。因为这样的图不仅会提供丰富的有意义的图例,此外还可通过研究其覆盖来研究更大阶数的图类中发挥重要作用。本文的主要是任务分析确定阶为8p2的5度对称图。
关于本文所使用的符号都是标准的,可参照( [14] [15] )。对于一个正整数n,我们用
和
分别表示n阶循环群和2n阶二面体群,用
表示正二十面体群,用
表示36阶G-弧传递5度图。为了方便起见,有时我们会如Atlas ( [14] )中那样用n和pn分别表示n阶循环群和pn阶初等交换群,用
表示一个n阶群。对于两个群N和H,用
表示N与H的直积,用
表示N被H的扩张,如果这个扩张是可裂的,则表示为
。此外,用
表示n阶完全图,
表示2n阶完全二部图,
示在
中去掉一个完全匹配所得的图。
定理1.1 设
是连通的阶为8p2的5度G-弧传递图,其中
,且p是奇素数,则下列表述成立:
1) 若G在
上是顶点拟本原时,存在一个72阶的5度弧传递图
,且
;
2) 若G在
上是顶点二部拟本原时,存在两个72阶的5度弧传递图
和
,且
;
定理1.2 设
是8p2阶连通的
-弧传递5度图其中p为素数,
为
的正规覆盖,且存在正规子群N,使得下述之一成立:
1)
,
;
2)
,
,其中
;
2. 预备知识
定义2.1 设G传递作用在集合
上,如果G不是非本原群,即不存在非平凡块,则称G为
上的本原群。
此外,本原群一定是传递群。
下面的这个定义是关于拟本原置换群是本原置换群概念的推广。
定义2.2 设G是一个传递置换群,如果G的每个极小正规子群都是传递的,则称G是拟本原的;如果G的每个极小正规子群至多有两个轨道且存在一个极小正规子群恰好有两个轨道,则称G是二部拟本原的。
定理2.3 ( [16] )设
是拟本原置换群,
,
。则G只有HA,AS,TW,SD,CD,PA,HS和HC八种类型:
1) 如果
是G的唯一极小正规子群,其中T为单群,此时分为以下六类:
a) HA (仿射型):如果N可交换,此时T为交换单群,从而
,于是
,因此N在
上正则,于是
。
b) 如果N是非交换群,此时,T为非交换单群。则有下述情形成立:
i) AS (几乎单型):若
,则
,于是
。
ii) TW (扭圈积型):若
在
上正则,其中
,则
。
iii) SD (单对角型):若
且
,其中
,则
。
iv) CD (复合对角型):若
且
,其中
,
,则
。
v) PA (乘积作用型):若
且
,其中
。
2) 如果G恰有两个极小正规子群M,N,且
,则
,其中T为非交换单群。
i) HS (全形单型):若
,则
。
ii) HC (复合全型):若
,则
。
在( [17], 定理1.1)和( [18] )中,5度连通对称图的点稳定子群被独立确定出来,其中
表示阶为n的Frobenius群,n为正整数。
定理2.4 设
是一个连通的5度
-弧传递图,其中
且
。若
,有
,且
,则下列结论成立:
1)
,
,
或
。
2)
,
,
,
或
。
3)
,
,
,
或
。
4)
,
,
,
,
。
5)
,
。
定理2.5 设 是一个素数度G-弧传递图,且设
在
上有两个以上的轨道,其中
。则下列结论成立。
1) N在
上半正则,
,
是
-弧传递的,且
是
的正规N-覆盖;
2)
是
-弧传递的当且仅当
是
-弧传递的,其中
或
;
3)
,其中
,
。
对于正整数n和群T,通常用
表示
的素因子集合,
表示
中含有素因子的个数。如果
则称群T为
-群。当
时,
-单群在( [19] )和( [20] )中被确定出来。
3. 定理1.1的证明
在本章节中,我们先证明以下三个引理,以此来完成定理1.1的完整证明。
引理3.1 设T是一非交换的单群,满足
且
,其中p为奇素数,则满足情况的单群有
和
。
证明:因为
,所以
,因此单群T满足( [20],定理1)。如果
,则
,因此T是一个{2,3,5}群。若
,则有
,由( [20],表1)可知,T同构于( [20],表1)中的八个群之一,即
,
或
。又
,则
或
。当
,我们有
,并且由
和( [20],表1)可知,此时不存在群T。
如果
,有
,且
,由此可知
(1)
由( [20],定理1)可知,T满足( [20],表2)或者
是一个含有4个素因子的群,其中q是一个素数的方幂。现在考虑前一种情形,如果T满足( [20],表2),对于( [20],表2)中的31个群,通过检查每个群的阶可得,群T不存在。
如果
,则
因此
如果
,则由( [20],定理3.2)可知:要么q是2,3,5或7的方幂,要么
是一个素数。对于后一种情形,有
此时,
,矛盾。所以现在我们只考虑第一种情形,根据( [20],表2)中的群,通过检查每个群的阶可得,群T不存在。
下面我们开始定理1.1的证明,主要是从G在
上是拟本原和二部拟本原两种情形来分析,从而来完成定理1.1的证明。
引理3.2 若G在
上是拟本原的,存在一个72阶5度弧传递图图
,且
。
证明:设N是G的一个极小的正规子群,则N为同构单群的直积,即
,其中
是一个单群。因为G在
上是拟本原,所以N在
上传递。如果N是交换的,则N在
半正则,从而
,矛盾,故N非交换。我们假设
。由
的连通性以及
,我们可知
是N-弧传递的。此时,如果
在
传递,由( [15],定理4.2)可知,
的中心化子
(即
)是半正则的,与
矛盾。如果
在
上至少有三条轨道,则由定理2.5可知
是半正则,矛盾。因此
在
上恰好有两条轨道,分别为U和W。又因为
,所以U和W则构成了一个N-不变划分,换句话说就是集合稳定子
在N中的指数为2,进一步由
中没有指数为2 的子群可知,矛盾,故
。
注意到
是T-弧传递,故
满足定理2.4.于是我们可由T的传递性可知,
。又
是T-弧传递,故
,即T满足引理3.1。由
,再由引理3.1可知,我们只需考虑
这种情形。
假设
,则我们由引理3.1可知,满足T和p2的只有群
或
。若
,则
,即
,利用Magma ( [21] )计算可得,图不存在。若
,则
,由引理2.4可知,
,由Magma ( [21] )计算可得,存在图
。
综上所述,G在
上是拟本原时存在图
。
引理3.3若G在
上是二部拟本原的,存在两个72阶的5度弧传递图
和
,且
。
证明:因为G在
上是二部拟本原的,所以G存在极小正规子群
,且在
上恰好有2个轨道,分别记作
和
。那么
和
是图
的两个部,因此
就是一个二部图。令
从而有
,且
,
。
若N交换,则N在
上正则的,从而
,不可能。因此N是非交换的。假设
作用在
和
上是不忠实的,根据( [22],引理5.2)可知,
是一个完全二部图。又
是5度图,则
,即
,与
矛盾,从而
作用在
和
上是忠实的。由( [23],定理1.5)可知
在
上是拟本原的或者
有两个正规子群
和
,使得
,且在
上半正则。进一步地,
在
上是正则的。
对于后一种情形,我们有
|,矛盾。
下面我们考虑前一种情形,由定理2.3可知,
是几乎单或乘积作用型。设
是
的基柱,其中T是非交换单群,且
。
若
是几乎单,则
。进一步,如果T不是G的唯一的极小正规子群,由于
,那么我们就很容易的得到
,于是G有正规子群
在
上有4p2个轨道,这与G在
上是二部拟本原的相矛盾。故T是G的唯一极小正规子群,即G是几乎单的,且其基柱
。令
,
,其中
,且
。
由于
,于是由定理2.4可知,
,因此
整除
。另一方面,由于
,我们有
,即T满足引理3.1.由
,再由引理3.1可知,我们只需考虑
这种情形。
若
时,由引理3.1可知,满足T和p2条件的群只有
或
。若
,则
。由Atlas ( [14] )可知,
,所以有
,
,且
,因此
。于是
,此外,再由定理2.4可得
。进一步,有
。于是我们利用Magma ( [21] )计算可知,此时不存在图
。若
,则
。由Atlas ( [14] )可知,
,所以
,
或
,
,故
或
,于是
或
。由定理2.4可知,
或
。分别由Magma ( [21] )计算可知,存在两个72阶的5度弧传递图
和
,且
。
假设
是乘积作用型的,则有
,其中
,
是一个单群。如果
在
上是传递的,我们由( [15] 定理4.2)可知,
是半正则的,因此
,矛盾。从而
在
和
上不传递,同样由( [24] 引理3.2)可知,
是半正则的,矛盾。
综上所述,G在
上是二部拟本原时,存在两个72阶的5度弧传递图
和
。
定理1.1的证明证毕。
4. 定理1.2的证明
在本节中,我们将利用定理1.1来分析关于定理1.1的一般研究的情形,以此来完成对定理1.2的证明。
证明:设
是8p2阶连通
-弧传递5度图,其中p是奇素数,
是
的正规覆盖。如果G在
上是拟本原或二部拟本原,则由引理3.2和引理3.3可知,G在
上是拟本原时存在图
,G在
上是二部拟本原时,存在两个72阶的5度弧传递图
和
。
下设G在
上既不是拟本原也不是二部拟本原,则G有一个极小正规子群N,即存在G的非平凡正规子群在
上至少有三条轨道。设G为G在
上至少有三个极小正规子群中的极大者。由定理2.5可知,N在
上半正则,
,
是
-弧传递5度图。此时,由N的及大性,
在
上拟本原或二部拟本原。又因为
,所以
。
下面对
进行分析。
1) 如果
,则
或
。由于p为奇素数,且
是奇数阶5度弧传递,从而与
矛盾。
2) 如果
,则
。由( [25],定理1)可知,不存在8阶5度对称图,所以
,与之矛盾。
3) 如果
,则
。由( [26],定理1.1)可知,
,且是唯一的36阶连通的5度对称图。
4) 如果
,则
。由( [27],引理1.5)知,
,其中
,
是一个阶为
的超特殊5-群,
,
,即
是一个阶为50的连通的5度对称图。
5) 如果
,则
。由( [26],引理1.5)知,
,且
。
6) 如果
,则
。由( [27],引理1.5),
,且
,其中
。由于
,因此
,故
,所以有
。由Sylow定理可知,G的Sylow p-子群的个数
满足
,因此
,故
,这与之前讨论(2)的情形相矛盾,证毕。
基金项目
国家自然科学基金资助项目资助(基金名称:若干传递图类及其相关问题研究,编号:11461007)。