4pqn阶3度对称图的分类
A Classification on Cubic Symmetric Graphs of Order 4pqn
DOI: 10.12677/PM.2019.910139, PDF, HTML, XML, 下载: 826  浏览: 3,122  国家自然科学基金支持
作者: 王 超:云南财经大学统计与数学学院,云南 昆明
关键词: 对称图局部本原拟本原二部拟本原几乎单Symmetric Graph Locally Primitive Quasiprimitive Bi-Quasiprimitive Almost Simple
摘要: 设Γ是一个连通图,G≤Aut(Γ),如果G作用在VΓ上是拟本原或顶点二部拟本原的,则称Γ是G-基图。在本文中,我们将4pqn阶3度对称G-基图,其中p < q为奇素数,n≥1。
Abstract: Let Γ be a connected graph and G≤Aut(Γ). Then Γ is called a G-basic graph, if G is quasiprimitive or bi-quasiprimitive on VΓ. In this paper, we determine cubic symmetric G-basic graphs of order 4pqn, where p < q are odd primes, and n≥1.
文章引用:王超. 4pqn阶3度对称图的分类[J]. 理论数学, 2019, 9(10): 1132-1138. https://doi.org/10.12677/PM.2019.910139

1. 引言

本文中所考虑的图都是连通的,无向的,无自环且无重边的。对于一个图 Γ ,我们用 V Γ A Γ Aut ( Γ ) 分别表示其顶点集,弧集和全自同构群。 | V Γ | 表示图 Γ 的阶(即 Γ 顶点的个数)。如果 Aut ( Γ ) 的一个子群G作用在 V Γ ( A Γ )是传递的,则称 Γ 是G-点传递的(G-弧传递的)。一个弧传递图也称为对称图。对一个正整数s, V Γ s + 1 个点 α 0 , α 1 , , α s 满足 α i 1 α i ( 1 i s )邻接且 α i 1 α i + 1 ( 1 i s 1 ),我们称 ( α 0 , α 1 , , α s ) Γ 的一条s-弧。如果 G Aut ( Γ ) 在s-弧集上是传递的,则称 Γ ( G , s ) -弧传递的。进一步,如果 G Aut ( Γ ) 在s-弧集上传递,在 s + 1 -弧集上不传递,那么 Γ 叫作 ( G , s ) -传递。

对阶数固定的对称图的研究一直是代数图论领域一个很热门的课题,例如,文献( [1] [2] [3] )分别分类了阶为p,2p和3p的对称图。对于一些小度数的图也有很多学者研究,更多文献可参考( [4] - [9] )。1947年,Tutte在文献( [10] )中给出了3度图的点稳定子结构。此后,3度对称图得到了很多学者的关注,例如:Feng等在文献( [4] )中刻画了两倍素数幂的3度对称图;Lu等在文献( [8] )中研究了阶为6p2的3度对称图;Zhou和Feng在( [11] )中分类了2pq阶的3度对称图。

G Sym ( Ω ) 是一个传递置换群,如果G的每个极小正规子群在 Ω 上都是传递的,则称G是拟本原的;如果G的每个极小正规子群在 Ω 上至多有两个轨道且存在一个极小正规子群在 Ω 上恰好有两个轨道,则称G是二部拟本原的。对于一个图 Γ G Aut ( Γ ) ,如果G在顶点集 V Γ 上是拟本原或二部拟本原的,则称 Γ 是一个G-基图。研究对称图的方法分为以下两步:

第一步,刻画基对称图;

第二步,研究基图的正规覆盖。

上述步骤我们可以看出对基图的刻画是研究对称图的基础,它对作基图的覆盖具有重要的参考作用。设 Γ 是阶为 4 p q n ( n 1 )的3度G-弧传递图,本文中我们刻画 Γ 的基图,其中p,q为素数且 3 p < q 。主要结论如下:

定理1.1 设 Γ 是阶为 4 p q n ()的3度G-弧传递图,其中p,q为素数且 3 p < q ,设 G Aut ( Γ ) V Γ 上是拟本原或二部拟本原的, α V Γ ,则 ( Γ , Aut ( Γ ) , G , s ) 满足表1

Table 1. G-basic symmetric graphs of order 4 p q n and valency 3

表1. 4 p q n 阶3度G-基对称图

关于本文中所使用的群论和图论的相关符号都是标准的,可参考文献( [12] [13] [14] )。例如:我们用 A n S n 分别表示n阶循环群,交错群和对称群。对于一个单群T,我们用 π ( T ) 表示 | T | 的素因子集合。

2. 预备知识

在本节中,我们给出一些与本文相关的定理和例子。首先是Tutte在1947年确定的3度对称图的点稳定子的结构,它是我们研究3度图的基础。

定理2.1 ( [10] ) 设 Γ 是一个连通的3度 ( G , s ) -弧传递图,则 s 5 ,则 ( G α , s ) 满足表2,其中 α V Γ

Table 2. Point-stabilizer groups of cubic symmetric groups

表2. 3度对称图的点稳定子

对于一个图 Γ ,如果点稳定子 Aut ( Γ ) α α 的邻域 Γ ( α ) 上是本原的,则称 Γ 为局部本原的,由于素

数度的弧传递图是局部本原的,因此下面的结论( [15],引理2.5)提供了研究局部本原图的基本方法,这个结论对Praeger的结果( [16],定理4.1)进行了改进。

定理2.2 ( [15] ) 设 Γ 是一个连通的奇素数度的G-弧传递图, G Aut ( Γ ) 有一个非传递正规子群N在 V Γ 上至少有三个轨道。则下列事实之一成立:

1) N在 V Γ 上半正则, G / N Aut ( Γ N ) Γ N G / N -弧传递的且 Γ Γ N 的正规N-覆盖;

2) Γ ( G , s ) -弧传递的当且仅当 ( G / N , s ) -弧传递的,其中 1 s 5 s = 7

3) G α ( G / N ) δ ,其中 α V Γ δ V Γ N

在文献( [16] )中,Praeger将拟本原置换群分为八类,我们将其称为O’Nan-Scott-praeger定理。下面我们简述O’Nan-Scott-praeger定理。

定理2.3 ( [16] )拟本原置换群可以分为以下八类:

HA (仿射型): soc ( X ) 是交换的,,其中p是素数,

HS (全形单型):,其中 N M T

HC (复合全型): soc ( X ) = M × N ,其中 N M T k

AS (几乎单型): soc ( X ) = T 是非交换单群, T X Aut ( T ) T . Out ( T )

TW (扭圈积型): Ω 上正则, | Ω | = | T | k ,其中 d 2

SD (单对角型): soc ( X ) = T k soc ( X ) α = T | Ω | = | T | k 1 ,其中 d 2 α Ω

CD (复合对角型): soc ( X ) = T k soc ( X ) α = T l | Ω | = | T | k l ,其中 l | k α Ω

PA (乘积作用型): soc ( X ) = T r soc ( X ) α 1 ,其中 α Ω

对于以下较小的群G,我们可以利用Magma ( [17] )确定所有同构意义下的弧传递图,并且得到下面的几个例子。

例2.4 (1) G = PSL ( 2 , 11 ) ,则G存在子群同构于 3 ,此时存在一个阶为220阶的3度对称图,记为 G 220 1

(2) G = PSL ( 2 , 11 ) ,则G存在子群同构于 S 3 ,此时存在一个阶为220阶的3度对称图,记为 Aut ( Γ ) PSL ( 2 , 11 )

例2.5 (1) G = PSL ( 2 , 13 ) ,则G存在子群同构于 3 ,此时存在一个阶为364阶的3度对称图,记为 G 364 1 Aut ( Γ ) PSL ( 2 , 13 )

(2) G = PSL ( 2 , 13 ) ,则G存在子群同构于 S 3 ,此时存在一个阶为364阶的3度对称图,记为 G 364 2 Aut ( Γ ) PSL ( 2 , 13 )

例2.6 G = PSL ( 2 , 23 ) ,则G存在子群同构于,此时存在一个阶为1012阶的3度对称图,记为 G 1012 1 Aut ( Γ ) PSL ( 2 , 23 )

例2.7 G = PSL ( 2 , 47 ) ,则G存在子群同构于 S 4 × 2 ,此时存在一个阶为4324阶的3度对称图,记为 G 4324 1

3. 定理1.1的证明

本节中,我们分以下三个引理来完成定理1.1的证明。

引理3.1 设T是一个非交换单群, | T | | 2 6 3 r s l ,且 3 r s l | | T | ,其中 3 r < s 为素数。则 T A 6 PSL ( 2 , 8 ) PSL ( 2 , 11 ) PSL ( 2 , 13 ) PSL ( 2 , 16 ) PSL ( 2 , 17 ) PSL ( 2 , 31 ) PSL ( 2 , 32 ) PSL ( 2 , 47 ) ,或 PSL ( 2 , 193 )

证明:由于有限p-群和 m a n b (m,n为素数,a,b为正整数)阶群都可解,而可解单群必为素数阶循环群,所以 | π ( T ) | 1 或2,因此 | π ( T ) | = 3 或4。如果 | π ( T ) | = 3 ,由文献( [12],定理1),T同构于( [12],表1)中的八个群之一,又因为 3 r s l | | T | 通过检查群的阶,满足条件的群只有 A 6 PSL ( 2 , 8 ) ,或 PSL ( 2 , 17 )

假设 | π ( T ) | = 4 。则 5 r < s | T | | 2 6 3 r s l 。由此可知

2 7 | T | , 3 2 | T | , r 2 | T | (1)

由文献( [12],定理1),T同构于( [12],表3)中的某个群或 PSL ( 2 , q ) ,其中q是一个素数幂。对于前一种情况,由于 3 r s l | | T | ,由( [12],表3)查得不存在满足条件的群。

如果 T PSL ( 2 , q ) ,则有 | T | = 1 2 q ( q 1 ) ( q + 1 ) | 2 6 3 r s l | π ( q 2 1 ) | = 3 ,因此 q = t e ,其中 e 1 t { 2 , 3 , 5 , s } 。如果 t { 2 , 3 , 5 } ,由式子(1)和 | π ( q 2 1 ) | = 3 可知, q = 2 4 或25,即 T PSL ( 2 , 16 ) ,或 PSL ( 2 , 32 ) ,如果 t = s ,此时有

1 2 ( q 1 ) ( q + 1 ) | 2 6 3 r

q 1 2 q + 1 2 | 2 5 3 r

我们注意到 ( q 1 2 , q + 1 2 ) = 1 ,于是 q 1 2 | 2 5 3 q + 1 2 | 2 5 3 ,因此q = 11,13,23,31,47,49,97或193。通过检查群的阶可得, T PSL ( 2 , 11 ) PSL ( 2 , 13 ) PSL ( 2 , 23 ) PSL ( 2 , 31 ) PSL ( 2 , 47 )

之后,我们总假设 Γ 是一个阶为 4 p q n ( 3 p < q , n 1 )的连通G-弧传递3度图,且G在 V Γ 上是拟本原或二部拟本原的,其中 G Aut ( Γ ) 。令 α V Γ

引理3.2 假设G在 V Γ 上是拟本原的,则 Γ F 084 G 220 1 G 364 1 G 1012 1 G 620 1 G 4324 1

证明:设N是G的一个极小正规子群。则N为同构单群的直积,即 N = T d = T 1 × T 2 × × T d ,其中 T i T ( i = 1 , , d )是一个单群。因为G在 V Γ 上拟本原,所以N在 V Γ 上是传递的。如果N是交换的,则N在 V Γ 上半正则,于是 | T | d = | N | | 4 p q n ,这是不可能的,故N是非交换的。首先我们断言 d = 1 。事实上,由 Γ 的连通性及,我们可知 Γ 是N-弧传递的。此时,如果 T 1 V Γ 上传递,由( [14],定理4.2A)可知 T 1 的中心化子 C N ( T 1 ) (即 T 2 )是半正则的,与 | T 2 | 4 p q n 矛盾。如果 V Γ 上至少有三个轨道,则由定理2.2可知 T 1 是半正则的,同样是一个矛盾。从而 T 1 V Γ 上恰好有两个轨道U和W。又因为 T 1 N ,因此U和W构成 V Γ 上一个N-不变划分,这就意味着集合稳定子 N U 在N中的指数为2,而 N = T d 中没有指数为2子群,矛盾。于是 N = T

因此 Γ 是T-弧传递的,故 T α 满足定理2.1。于是由T的传递性可以得到, | V Γ | | T α | = | T | | 2 6 3 p q n 。又因为 Γ 是T-弧传递的,故 3 | | T α | ,从而 3 p q n | | T | ,即T满足引理3.1。

假设,则T和表3所示。

Table 3. Nonabelian groups with 3 prime factors and ( p , q n )

表3. 含有3个素因子的单群及对应 ( p , q n ) 取值

如果 T A 6 ,则 | T α | = | T | / | V Γ | = 6 ,即 T α S 3 。由Magma ( [17] )计算可得,满足条件的图不存在。如果 T PSL ( 2 , 8 ) ,则 | T α | = | T | / | V Γ | = 6 ,即 T α S 3 。由文献( [18] )可知 Γ F 084 ,如果 T PSL ( 2 , 17 ) ,则 | T α | = | T | / | V Γ | = 12 ,即 T α S 3 × 2 。但是 PSL ( 2 , 17 ) 中没有子群同构于 S 3 × 2 ,这是不可能的。

假设 | π ( T ) | = 4 ,则T和 ( p , q n ) 表4所示。

Table 4. Nonabelian groups with 4 prime factors and ( p , q n )

表4. 含有4个素因子的单群及对应 ( p , q n ) 取值

如果 T PSL ( 2 , 11 ) ,则 | T α | = | T | / | V Γ | = 3 ,即 T α 3 ,由例2.4可知 Γ G 220 1 。如果 T PSL ( 2 , 13 ) ,则 | T α | = | T | / | V Γ | = 3 ,即 T α 3 。由例2.5可知 Γ G 364 1 。如果 T PSL ( 2 , 2 4 ) ,则 | T α | = | T | / | V Γ | = 12 ,即 T α S 3 × 2 ,但 PSL ( 2 , 2 4 ) 中没有同构于 S 3 × 2 的12阶子群。如果,则 | T α | = | T | / | V Γ | = 6 ,即,由例2.6可知 Γ G 1012 1 。如果 T PSL ( 2 , 31 ) ,则 | T α | = | T | / | V Γ | = 24 ,即 T α S 4 ,由文献( [18] )可知 Γ F 620 * 。同样地,由例2.7可以得到 Γ G 4324 1 ,此时 T PSL ( 2 , 47 ) T α S 3 × 2 。而对于 T PSL ( 2 , 2 5 ) T PSL ( 2 , 193 ) ,有 T α S 4 S 4 × 2 ,但是对应的T都没有子群同构于 S 4 × 2

引理3.3 G在 V Γ 上是二部拟本原的,则 Γ G 220 2 ,或 G 364 2

证明:因为G在 V Γ 上二部拟本原,所以G存在极小正规子群 N = T d V Γ 上恰好有两个轨道 Δ 1 Δ 2 ,那么 Γ 就是一个二部图。令 G + = G Δ 1 = G Δ 2 ,则有 N G + | G : G + | = 2 G α = G α + 。假设 G + 作用在 Δ 1 上是不忠实的,由( [19],引理5.2),是一个完全二部图,又因为 Γ 为3度图,则 Γ K 3 , 3 ,即 | V Γ | = 6 ,与 | V Γ | = 4 p q n 矛盾。从而 G + 作用在 Δ i ( i = 1 , 2 )上忠实,由( [20],定理1.5)可知,下述之一成立:

1) G + Δ i 上是拟本原的;或

2) G + 中存在两个正规子群 M 1 ,使得 M 1 M 2 且在 V Γ 上半正则。进一步地,有群 M = M 1 × M 2 Δ i 上是正则的。

对于(2),我们可以得到 | M | = | M 1 | 2 = 2 p q n ,这是不可能的。

故(1)成立,因为 | Δ i | = 2 p q n ,由定理2.3可知, G + 是几乎单或乘积作用型。设 N = soc ( G + ) = T d G + 的基柱。其中T是非交换单群且

假设 G + 是几乎单的,因此 soc ( G + ) = T 。进一步地,如果T不是G唯一的极小正规子群,由于 G = G + . 2 ,我们很容易可以得到 G = G + × 2 ,也就是说G有正规子群 2 V Γ 上有 2 p q n 个轨道,与G的二部拟本原性矛盾。从而G是几乎单的,设 soc ( G ) = T 。因此我们可以令 G = T . o G + = T . o ,其中 | o : o | = 2

因为 T α G α ,由定理2.1可知 | T α | | 2 4 3 ,因此。另一方面,由于 T α 1 ,我们可以得到 ,从而 3 p q n | | T | ,故T满足引理3.1且 | π ( T ) | = 3 或4。

| π ( T ) | = 3 时,则T和 ( p , q n ) 满足表3。如果,则 | T α | = | T | / | Δ i | = 12 。因为 Out ( A 6 ) = 2 2 ,所以 o = 2 o = 1 o = 2 2 o = 2 。故 | G α | = | G α + | = | T α | | o | = 12 或 , G S 6 Aut ( A 6 ) 。由Magma ( [17] ),这两种情况下都没有图存在。如果 T PSL ( 2 , 8 ) ,因为 Out ( PSL ( 2 , 8 ) ) = 3 没有指数为2的子群,与 | o : o | = 2 矛盾。如果 T PSL ( 2 , 17 ) ,因为 Out ( PSL ( 2 , 17 ) ) = 2 | T α | = | T | / | Δ i | = 24 ,所以 | G α | = | G α + | = | T α | | o | = 24 G PSL ( 2 , 17 ) . 2 = PGL ( 2 , 17 ) ,由Magma ( [17] ),不存在满足条件的图 Γ

| π ( T ) | = 4 时, ( T , p , q n ) 满足表4。如果 T PSL ( 2 , 193 ) ,则 | T α | = | T | / | Δ i | = 96 ,从而。这与定理2.1矛盾。如果 T PSL ( 2 , 32 ) ,则 Out ( T ) = 5 ,因为 | o : o | = 2 ,矛盾。如果 T PSL ( 2 , 2 4 ) ,则 | T α | = | T | / | Δ i | = 24 。因为,故 G PGL ( 2 , 16 ) Aut ( PSL ( 2 , 16 ) ) ,且对应的 G α 分别为 S 4 × 2 ,由Magma ( [17] )可知 PGL ( 2 , 2 4 ) 中没有24阶子群,中没有同构于 S 4 × 2 的48阶子群,矛盾。如果 T PSL ( 2 , 31 ) ,则 | T α | = 48 。又因为 Out ( PSL ( 2 , 31 ) ) = 2 ,所以 G PGL ( 2 , 31 ) 。与 PGL ( 2 , 31 ) 中没有48阶子群矛盾。若 T PSL ( 2 , 23 ) 时,由Magma ( [17] ),不存在这样的3度对称图。若 T PSL ( 2 , 11 ) PSL ( 2 , 13 ) ,由例2.4和2.5可知, Γ G 220 2 G 364 2

假设 G + 是乘积作用型的,则 N = T d = T 1 × T 2 × × T d ( d 2 ) ,其中 ( i = 1 , , d )是一个单群。如果上是传递的,由( [14],定理4.2A)可知 T 2 是半正则的,故 | T 2 | | 2 p q n ,矛盾。从而 T 1 Δ 1 上都不传递,由( [8],引理3.2)可知 T 1 是半正则的,同样可以推出矛盾。

基金项目

国家自然科学基金资助项目(80031010061)资助。

参考文献

[1] Chao, C.Y. (1971) On the Classification of Symmetric Graphs with a Prime Number of Vertices. Transactions of the American Mathematical Society, 158, 247-256.
https://doi.org/10.2307/1995785
[2] Cheng, Y. and Oxley, J. (1987) On Weakly Symmetric Graphs of Order Twice a Prime. Journal of Combinatorial Theory, Series B, 42, 196-211.
https://doi.org/10.1016/0095-8956(87)90040-2
[3] Wang, R.J. and Xu, M.Y. (1993) A Classification of Symmetric Graphs of Order 3p. Journal of Combinatorial Theory, Series B, 58, 197-216.
https://doi.org/10.1006/jctb.1993.1037
[4] Feng, Y.Q. and Kwak, J.H. (2006) Cubic Symmetric Graphs of Order Twice an Odd Prime Power. Journal of the Australian Mathematical Society, 81, 153-164.
https://doi.org/10.1017/S1446788700015792
[5] Feng, Y.Q. and Kwak, J.H. (2007) Cubic Symmetric Graphs of Or-der 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
[6] Feng, Y.Q., Zhou, J.X. and Li, Y.T. (2016) Pentavalent Symmetric Graphs of Order Twice a Prime Power. Discrete Mathematics, 339, 2640-2651.
https://doi.org/10.1016/j.disc.2016.05.008
[7] Hua, X.H., Chen, L. and Xiang, X. (2018) Valency Seven Symmetric Graphs of Order 2pq. Czechoslovak Mathematical Journal, 68, 581-599.
https://doi.org/10.21136/CMJ.2018.0530-15
[8] Lu, Z.P., Wang, C.Q. and Xu, M.Y. (2004) On Semisymmetric Cubic Graphs of Order 6p2. Science in China Series A Mathematics, 47, 1-17.
[9] Zhou, J.X. and Feng, Y.Q. (2010) Tetravalent s-Transitive Graphs of Order Twice a Prime Power. Journal of the Australian Mathematical Society, 88, 277-288.
https://doi.org/10.1017/S1446788710000066
[10] Tutte, W.T. (1947) A Family of Cubical Graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 43, 459-474.
https://doi.org/10.1017/S0305004100023720
[11] Zhou, J.X. and Feng, Y.Q. (2010) Cubic Vertex-Transitive Graphs of Order 2pq. Journal of Graph Theory, 65, 285-302.
https://doi.org/10.1002/jgt.20481
[12] Huppert, B. and Lempken, W. (2000) Simple Groups of Order Divisible by at Most Four Primes. Francisk Skorina Gomel State University, 16, 64-75.
[13] 徐明耀. 有限群导引(上, 下)[M]. 北京: 科学出版社, 1999.
[14] Dixon, J. and Mortimer, D.B. (1997) Permutation Groups. Spring-Verlag, New York.
https://doi.org/10.1007/978-1-4612-0731-3
[15] Li, C.H. and Pan, J.M. (2008) Finite 2-Arc-Transitive Abelian Cayley Graphs. European Journal of Combinatorics, 29, 148-158.
https://doi.org/10.1016/j.ejc.2006.12.001
[16] Praeger, C.E. (1992) An O’Nan-Scott Theorem for Finite Quasiprimitive Permutation Groups and an Application to 2-Arc-Transitive Graphs. Journal of the London Mathematical Society, 47, 227-239.
https://doi.org/10.1112/jlms/s2-47.2.227
[17] 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
[18] Conder, M. and Dobcsabyi, P. (2002) Trivalent Symmetric Graphs on up to 768 Vertices. Journal of Combinatorial Mathematics and Combinatorial Computing, 40, 41-63.
[19] Giudici, M., Li, C.H. and Praeger, C.E. (2003) Analysing Finite Locally s-Arc-Transitive Graphs. Transactions of the American Mathematical So-ciety, 356, 291-317.
https://doi.org/10.1090/S0002-9947-03-03361-0
[20] Li, C.H., Praeger, C.E., Venkatesh, A. and Zhou, S.M. (2002) Finite Locally-Quasiprimitive Graphs. Discrete Mathematics, 246, 197-218.
https://doi.org/10.1016/S0012-365X(01)00258-8