1. 引言
在群与图研究领域中,1-正则图一直是一个主要研究对象。自1952年R. Frucht在文献 [1] 中给出第一个3度1-正则图的例子后,Marusic,Malnic等人在文献 [2] [3] 构造出了两类不同的4度1-正则图的无限族。而文献 [4] 中给出连通3度Cayley图是1-正则图的一个充要条件,并利用交错群
分别构造了连通3度1-正则和2-正则Cayley图的无限族。而文献 [5] 则显示了3度1-正则图在地图上的一些重要应用。
本文主要尝试对于每一个奇素数p,分类无核的p度1-正则Cayley图。
具体的,设
为
-正则Cayley图,其中
。记
。则H作用在S上正则且
。本文对G在X中是无核的情形做分类研究。
2. 引理
由文献 [6] (性质3.2),有下面的命题:
命题2.1设p为奇素数,
为p度
-正则Cayley图,其中
。设
。则存在对合
满足
,使得
,
,
。■
下面的引理给出,当X为奇素数级的本原置换群且H为其循环正则子群时,则X和H完全被确定。注意到
为p度
-正则Cayley图,由文献 [7] (推论1.2),得到如下引理:
引理2。1设p为奇素数,若X为p级本原置换群且X包含循环正则子群H,则:
1)
;
2)
,且
;
3)
或者
,其中
。
证明:由文献 [7] (推论1.2),仅需排除
和
的情形。由于p为奇素数,所以前者不可能发生。若
为仿射型本原置换群。由于
且
,我们有
与
为
-正则Cayley图矛盾。■
下面的引理给出当X为
或者
时,其极大子群的分类。由文献 [8] 或者文献 [9],容易得到下面的引理:
引理2.2设
为素数,若
或者
。令G为X的极大子群满足
。则
或者G为几乎单型的本原置换群。■
令N为X的包含在G的极大正规子群,也就是,
。由文献 [6] (性质2.1)有下面的引理:
引理2.3设p为奇素数,
为p度
-正则Cayley图,其中
。令
。则:
1) 若
,则
且
。
2) 若
,则存在
,其中
,
且
。
3)
;
为
的无核
-正则Cayley图且
为
的正规覆盖。
此外,
。■
3. 主要结论
定理3.1设
为p度1-正则Cayley图,其中p为奇素数。令
,若
,则
同构意义下为表1所列图之一。
Table 1. Core-free 1-regular Cayley graphs of valency p
表1. 无核p度1-正则Cayley图
注3.1在表1最后一行,
其中
且d为素数。
。此外,在表1的第四列中,
表示互不同构图的个数。
证明:设
为p度
-正则Cayley图,其中p为奇素数,
。设G在X中无核。注意到
。考虑X在集合
上的右乘作用,则作用忠实传递。此时,X为p级传递置换群。在这个作用下,X本原且包含循环正则子群H。由引理2.1,我们有以下几个选择
,
或者
,或者,
,且
。我们首先判断图的存在性,由性质2.1,仅需考虑
中对合的存在性。
1) 设
。则
且G在X中的指数为11。设M为X的极大子群满足
。由文献 [10],X的极大子群有:
,
,
。另一方面,
,所以
。显然有
,因而
。注意到
,2不整除
,所以存在对合
。我们声称
若不然,
包含在X的一个极大子群
里,由于
且X的所有极大子群为:
,
,
因而
,这与
矛盾。故,
。另一方面,
,由
的极大子群结构,我们有
。下面我们考虑这种情形下,存在互不同构图的个数。令
,
。为了方便证明,我们不妨设
。令
。则
。令
。则
。有文献 [10],X的所有对合在
的共轭作用下仅有一个轨道,因而同构意义下,这种情况下只存在一个图。此时,我们可以设
。令
。由MAGMA的计算,此时
。由于
,因而在这种情形下不存在无核p度1-正则Cayley图。
2) 设
。设M为X中包含
的极大子群。由文献 [10],X的极大子群有:
。由于
,也就是
,因而
。由本定理1) 的证明我们有
。显然存在2阶元
,进一步的我们可以在
里面取得
。若不然,
包含了
的所有对合。设
的所有对合生成的子群为P,此时
且
,与
为单群矛盾。若
,则
,其中
为
的极大子群。又
,故
,因而
这与
矛盾。所以,
。令
,
。令
。令
,
。则
,
。令
,
,
则X的包含
的极大子群
。另一方面,对合
,因此满足条件的
共110个且在
的共轭作用下恰好为2个轨道。不妨设其代表元素为:
。下面我们考虑图
和
。通过MAGMA的计算,我们有
,
且
与
互不同构,因此在这种情形下存在两个互不同构的无核11度1-正则Cayley图。最后,由于G在X中的指数为11,从X的所有极大子群结构我们得到
。
3) 设
此时,
。另一方面
的所有极大子群为(由 [10] ):
,
,
,
,
,
,
。设
为
中包含
的极大子群。由于
,也就是
。通过计算
极大子群的阶可以得到
。显然
,所以
。此时,与1) 类似的讨论,我们可以得到存在对合
使得
。注意到
,通过计算
极大子群在
中的指数得到
。另一方面,由MAGMA的计算,
中所有对合在
的共轭作用下恰好产生15个轨道。因此,在这种情形下我们得到互不同构图的个数
。
4) 设
,且
。此时
且
,其中
。此时,由文献 [11],我们可以得到
。下面设M为
中包含
的极大子群。则存在2-元素
。若不然,M包含了
的所以Sylow2-子群。设
为
的所有Sylow2-子群。则显然有
且
。故
,这与M为
的极大子群矛盾。另一方面,由M的极大性及
,有
。此外,由文献 [12] (注10.11),有d必为素数。
5) 设
其中
为素数。由于
且
,因而
。也就是
。设M为X的极大子群满足
。如果
。则显然存在奇置换的2阶元
(此时
)使得
。因此,陪集图
即为满足我们条件的Cayley图。下面我们假设
。由引理2.2,
或者M为作用在
的几乎单型本原置换群。我们先假设
。注意到
,因而
。此时显然有
,所以
。因为M为X的极大子群,因而存在对合
满足
。下面我们假设M为几乎单型本原置换群。此时亦存在对合
使得
。若不然,M包含了X的所以2阶元。设X的所以2阶元生成的子群为P,则
且
。另一方面,
的所有非单位元群正规子群为:
,
。这使得
,与M为X的极大子群且
矛盾。
6) 我们最后设
,其中
为素数。由于在X中指数为p的子群同构于
,所以
。设M为X中包含
的极大子群。由引理2.2,我们有
。显然存在对合
使得
。若不然,
其中
为X的极大子群。而
为素数,引理2.2显示
只能为
,也就是
这与
矛盾。因而,
即为满足我们条件的Cayley图。■
基金项目
国家自然科学基金项目(12061089,11701503);云南省教育厅科学研究基金项目(2017ZZX086)。