3度非弧传递无核Cayley图
Core-Free Nonsymmetric Cayley Graphs of Valency 3

作者: 李婉婷 , 凌 波 :云南民族大学数学与计算机科学学院,云南 昆明;

关键词: 无核Cayley图单群自同构群正规Cayley图Core-Free Cayley Graph Simple Group Automorphism Group Normal Cayley Graph

摘要:
设Γ=Cay(G,S)是群G上的Cayley图。称Γ为无核的,如果G在X中是无核的,其中G≤X≤AutΓ。用H表示1∈VΓ在X中的点稳定子。本文对H=16时,度数为3的非弧传递图Γ进行分类研究。

Abstract: Let Γ=Cay(G,S) be a Cayley graph of group G. Then Γ is said to be core-free if G is core-free in X, where G≤X≤AutΓ. Let H be the stabilizer of 1∈VΓ in X. We classify the 3-valent nonsymmetric Cayley graphs where H=16 in this paper.

1. 引言

本文仅讨论有限,简单,连通,无向图。

Γ 是一个图,其顶点集,边集,弧集,图的全自同构群分别记为 V Γ E Γ A r c Γ A u t Γ 。设 X A u t ( Γ ) ,我们称图 Γ 为X-点传递的,X-边传递的,X-弧传递的,如果X传递地作用在 V Γ E Γ A r c Γ 。相应地,称图 Γ 是点传递的,边传递的,弧传递的,如果 X = A u t ( Γ )

设G是一个有限群并记其单位元为1。取 S G { 1 } ,称它为G的Cayley子集。设S满足 S = S 1 : = { s 1 | s S } 。定义群G关于S的Cayley无向图 Γ : = C a y ( G , S ) ,其中:

V Γ : = G , E Γ : = { { g , s g } | g G , s S }

我们称Cayley图 Γ = C a y ( G , S ) 关于G是正规的,如果 G A u t Γ 。记 A u t ( G , S ) = { α A u t ( G ) | S α = S } ,记 A 1 是顶点1的点稳定子群。由文献 [1] (命题4.22),我们有, N A u t Γ ( G ) = G : A u t ( G , S ) 。所以, Γ 是正规Cayley图当且仅当 A 1 = A u t ( G , S ) ,当且仅当 A u t Γ = G : A u t ( G , S ) 。由此可见,正规Cayley图的全自同构群可被原群完全决定。

单群上的Cayley图,对于非弧传递图,目前相关的结论还是非常少。本文尝试做一些研究。

2. 预备知识

设X是任意有限群,H为G的无核子群。设D是H的双陪集的并,满足 D 1 = D 。定义陪集图 Cos ( X , H , D ) ,其顶点集 [ X : H ] : = { H x | x X } 使得 H x H y 相邻当且仅当 y x 1 H D H 。考虑X依右乘作用在H的右陪集集合 [ X : H ] 上。注意到该作用是忠实的且保持陪集图的邻接关系,我们可以将X看作图 Cos ( X , H , D ) 的全自同构群 A u t ( Cos ( X , H , D ) ) 的一个子群。显然, Cos ( X , H , D ) 是连通的当且仅当 D = X Cos ( X , H , D ) 的度数为 | D : H | 。容易验证H有n个轨道当且仅当D是n个H的双陪集的并。进一步,下面是关于陪集图性质的熟知的引理,其证明可参考文献 [2] [3] [4]。

引理2.1.设 Cos ( X , H , D ) 的定义如上,则

(1) 若 Cos ( X , H , D ) 是X-对称图,其度数至少为3,则存在元素 g X H 使得 g 2 H H , g = X 。更进一步,我们选择g为一个2-元素。

(2) 设 Γ = C a y ( G , S ) 是Cayley图且有 G X A u t ( Γ ) 。设 H = X α α V Γ 在X中的点稳定子,我们有 Γ Cos ( X , H , H S H )

(3) 相反地,设 Cos ( X , H , D ) 是陪集图,G是H在X中的补。记 S = G D 。则Cayley图 Γ = C a y ( G , S ) 同构于 Cos ( X , H , D ) ,因此 | S | = | D : H | 。特别地,如果 Γ 的度数为奇数,S包含G的对合。

N = C o r e X ( G ) 是G在X中的核。由文献 [2],我们容易得出下列结论。

引理2.2. 设 Γ = C a y ( G , S ) 是3度Cayley图, G X A u t ( Γ ) 。令 N = C o r e X ( G ) 。用 X 1 表示 1 V Γ 在X中的点稳定子。则下列之一成立:

(1) 若 G = N ,则 X G : A u t ( G , S ) X 1 A u t ( G , S )

(2) 若 | G : N | = 2 ,则存在 D N ,其中 1 D D = N Γ B i C a y ( N , D )

(3) 若 | G : N | > 2 ,N在 V Γ 上至少有3个轨道,则 Γ N 是关于 G / N 的Cayley图并且是无核的。

注2.2. (a) 若我们限制一些条件,上述引理中有些情形将不会成立。例如,当G是非交换单群时,(2)不会出现。

(b) 在情形(3)中,若 N = 1 ,则通过考虑X在 [ X : G ] (G在X中右陪集的集合)上的右乘作用,我们可将X视为对称群 S n ( n = | X : G | ) 的子群,X包含 S n 的一个同构于H (X作用 V Γ 上的一个点稳定子群)的正则子群;对 [ X : G ] 中的陪集重新标号为 1 , 2 , , n ,则G为X作用在 { 1 , 2 , , n } 上的一个点稳定子。

引理2.3. 设 Γ = C a y ( G , S ) 是连通无核3度非对称Cayley图,其中 G X A u t ( Γ ) 。设H是 1 V Γ 的点稳定子。则存在一个对合 x 1 N X ( H ) 和2-元素 x 2 N X ( H H x 2 ) x 1 x 2 不全包含于 U 1 K H N X ( K ) ,使得 Γ Cos ( X , H , H x 1 H H x 2 H ) S = G ( H x 1 H H x 2 H )

3. 主要结论

Γ = C a y ( G , S ) 是无核(关于G) 3度非弧传递Cayley图,其中 G X A u t ( Γ ) 。用H表示 1 V Γ 在X中的点稳定子。注意到 Γ 是3度非弧传递的,可知H一定是2-群,则有下面的结论:

定理3.1. 设 | H | = 16 。则下列之一成立:

(1) H同构于 Z 2 × D 8

(2) H同构于 Z 2 × Q 8

(3) 不存在无核3度非弧传递Cayley图。

Γ = C a y ( G , S ) 是无核(关于G) 3度非弧传递Cayley图,其中 G X A u t ( Γ ) H = X 1 表示 1 V Γ 在X中的点稳定子。设 D = H x 1 H H x 2 H P = H H x 2 。由引理2.3,我们有 Γ Cos ( X , H , D ) ,其中对合 x 1 N X ( H ) ,2-元素 x 2 N X ( P ) x 1 x 2 不全包含于 U 1 K H N X ( K ) 。更进一步有 x 1 , x 2 , H = X S = G D 。则P在H中的指数为2。

证明:注意到 | H | = 16 ,由MAGMA [5] 和GAP [6] 可知,对于H,存在14种可能的情形,也就是, H Z 16 , Z 4 × Z 4 ( Z 4 × Z 2 ) : Z 2 Z 4 : Z 4 Z 8 × Z 2 Z 8 : Z 2 D 16 Q D 16 Q 16 Z 4 × Z 2 × Z 2 Z 2 × D 8 Z 2 × Q 8 ( Z 4 × Z 2 ) : Z 2 Z 2 × Z 2 × Z 2 × Z 2 。我们将对它们一一进行分析。

首先,令 Ω : = { 1 , 2 , 3 , , 16 } 。由前段分析,X同构于对称群 S 16 的一个子群。假设 H Z 16 ,则 P Z 8 。因为 Γ 是3度图, | H : P | = 2 ,注意到循环群的所有子群均为全不变子群,于是 P c h a r H 。由于 x 1 N X ( H ) x 2 N X ( P ) ,则 P x 1 = P 。因此, P x 1 , x 2 , H = X ,换句话说,不存在无核3度非弧传递Cayley图。

假设 H Z 4 × Z 4 ,则 P Z 4 × Z 2 。注意到H和P均只有一个同构于 Z 2 × Z 2 的4阶子群,记为K,则K是H和P的特征子群。又因为 x 1 N X ( H ) x 2 N X ( P ) ,这意味着 K x 1 = K K x 2 = K ,所以 K x 1 , x 2 , H = X ,矛盾于H在X中无核。

假设 H ( Z 4 × Z 2 ) : Z 2 ,则 P Z 4 × Z 2 Z 2 × Z 2 × Z 2 。若 P Z 2 × Z 2 × Z 2 ,因为 H x 1 = H 且P是H中唯一同构于 Z 2 × Z 2 × Z 2 的子群,这意味着 P x 1 = P 。另一方面,由于 P x 2 = P P H ,我们有 P x 1 , x 2 , H = X ,矛盾。若 P Z 4 × Z 2 ,由MAGMA和GAP可知,不存在满足条件的 x 2 使得 Γ 是无核(关于G) 3度非弧传递Cayley图。

假设 H Z 4 : Z 4 ,则 P Z 4 × Z 2 。同样地,与 H Z 4 × Z 4 的情形有相同的讨论,推出矛盾。

假设 H Z 8 × Z 2 ,则 P Z 4 × Z 2 Z 8 。先假设前者成立,也即, P Z 4 × Z 2 。因为 H x 1 = H 且P是H中唯一同构于 Z 4 × Z 2 的子群,这意味着 P x 1 = P 。另一方面,由于 P x 2 = P P H ,我们有 P x 1 , x 2 , H = X ,矛盾。现设 H = a × b Z 8 × Z 2 P = a Z 8 ,其中 a = ( 1 12 4 10 2 11 3 9 ) ( 5 16 8 14 6 15 7 13 ) b = ( 1 5 ) ( 2 6 ) ( 3 7 ) ( 4 8 ) ( 9 13 ) ( 10 14 ) ( 11 15 ) ( 12 16 ) 。注意到P中只有一个4阶子群同构于 Z 4 ,也即, a 2 ,则 a 2 c h a r a = P H ,于是 a 2 H 。因为 x 2 N X ( P ) ,我们有 a 2 x 2 = a 2 。因为H中有两个8阶子群同构于 Z 8 ,也即, a a b ,因为 x 1 N X ( H ) ,那么 a x 1 = a a b 。若 P x 1 = a x 1 = a = P ,又 x 2 N X ( P ) ,推出 P x 1 , x 2 , H = X ,矛盾。注意到H中有两个4阶子群同构于 Z 4 ,也即, a 2 a 2 b ,因为 x 1 N X ( H ) ,那么 a 2 x 1 = a 2 a 2 b 。若 a x 1 = a b ,注意到 a 2 = ( a b ) 2 = ( 1 4 2 3 ) ( 5 8 6 7 ) ( 9 12 10 11 ) ( 13 16 14 15 ) ,我们有 a 2 x 1 = ( a b ) 2 = a 2 。因此 a 2 x 1 , x 2 , H = X ,这与H在X中无核矛盾。

假设 H Z 8 : Z 2 ,则 P Z 4 × Z 2 Z 8 。同样地,与 H Z 8 × Z 2 的情形相同的讨论,推出矛盾。

假设 H D 16 ,则 P D 8 Z 8 。注意到H中只有一个同构于 Z 4 的4阶子群。由MAGMA和GAP, D 8 Z 8 均是只有一个同构于 Z 4 的4阶子群,令 K Z 4 。所以K是H和P的特征子群。由于 x 1 x 2 的选择, K x 1 , x 2 , H = X ,矛盾。

假设 H Q D 16 ,则 P Q 8 Z 8 D 8 。注意到H中分别只有一个同构于 Q 8 Z 8 D 8 的8阶子群。所以当P为以上三种子群中的任何一种时,我们有 P c h a r H 。另一方面,由于 x 1 N X ( H ) x 2 N X ( P ) ,则有 P x 1 = P ,因此我们推出 P x 1 , x 2 , H = X ,矛盾。

假设 H Q 16 ,则 P Q 8 Z 8 。注意到H中只有一个2阶子群同构于 Z 2 。由MAGMA和GAP, Q 8 Z 8 均是只有一个同构于 Z 2 的子群,令 K Z 2 。所以K是H和P的特征子群。从而必有 K X ,矛盾。

假设 H Z 4 × Z 2 × Z 2 ,则 P Z 4 × Z 2 Z 2 × Z 2 × Z 2 。若 P Z 2 × Z 2 × Z 2 ,因为 H x 1 = H 且P为H中唯一同构于 Z 2 × Z 2 × Z 2 的子群,这意味着 P x 1 = P 。另一方面,由于 P x 2 = P P H ,于是 P x 1 , x 2 , H = X ,矛盾。若 P Z 4 × Z 2 ,由MAGMA和GAP可知,不存在满足条件的 x 2 使得 Γ 是无核(关于G) 3度非弧传递Cayley图。

假设 H ( Z 4 × Z 2 ) : Z 2 ,则 P D 8 Q 8 Z 4 × Z 2 。由MAGMA和GAP可知,不存在满足条件的 x 2 使得 Γ 是无核(关于G) 3度非弧传递Cayley图。

假设 H Z 2 × Z 2 × Z 2 × Z 2 ,则 P Z 2 × Z 2 × Z 2 。设 H = a , b , c , d ,其中

b = ( 1 5 ) ( 2 6 ) ( 3 7 ) ( 4 8 ) ( 9 13 ) ( 10 14 ) ( 11 15 ) ( 12 16 ) ,

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

d = ( 1 2 ) ( 3 4 ) ( 5 6 ) ( 7 8 ) ( 9 10 ) ( 11 12 ) ( 13 14 ) ( 15 16 ) .

我们断言a是由b,c和d决定的。设 P = b , c , d 。显然P在 Ω 上半正则,且有两个轨道,记为 Δ 1 = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } Δ 2 = { 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 } 。因为H在 Ω 上是正则的,则 Δ 1 a = Δ 2 。可以发现 Σ 1 = { 1 , 5 } Σ 2 = { 2 , 6 } Σ 3 = { 3 , 7 } Σ 4 = { 4 , 8 } Σ 5 = { 9 , 13 } Σ 6 = { 10 , 14 } Σ 7 = { 11 , 15 } Σ 8 = { 12 , 16 } 是b在 Ω 上的8个轨道; Σ 1 = { 1 , 3 } Σ 2 = { 2 , 4 } Σ 3 = { 5 , 7 } Σ 4 = { 6 , 8 } Σ 5 = { 9 , 11 } Σ 6 = { 10 , 12 } Σ 7 = { 13 , 15 } Σ 8 = { 14 , 16 } 是c在 Ω 上的8个轨道; Σ 1 = { 1 , 2 } Σ 2 = { 3 , 4 } Σ 3 = { 5 , 6 } Σ 4 = { 7 , 8 } Σ 5 = { 9 , 10 } Σ 6 = { 11 , 12 } Σ 7 = { 13 , 14 } Σ 8 = { 15 , 16 } 是d在 Ω 上的8个轨道。回忆到 Δ 1 a = Δ 2 ,我们有 ( Σ i ) a = Σ j ( Σ i ) a = Σ j ( Σ i ) a = Σ j ,其中 i = 1 , 2 , 3 , 4 j = 5 , 6 , 7 , 8 。通过计算可知,a的所有可能的情况有8种,将其记为集合M,

M = { ( 1 9 ) ( 5 13 ) ( 3 11 ) ( 2 10 ) ( 6 14 ) ( 4 12 ) ( 7 15 ) ( 8 16 ) , ( 1 10 ) ( 5 14 ) ( 3 12 ) ( 2 11 ) ( 6 15 ) ( 4 13 ) ( 7 16 ) ( 8 9 ) , ( 1 11 ) ( 5 15 ) ( 3 13 ) ( 2 12 ) ( 6 16 ) ( 4 14 ) ( 7 9 ) ( 8 10 ) , ( 1 12 ) ( 5 16 ) ( 3 14 ) ( 2 13 ) ( 6 9 ) ( 4 15 ) ( 7 10 ) ( 8 11 ) , ( 1 13 ) ( 5 9 ) ( 3 15 ) ( 2 14 ) ( 6 10 ) ( 4 16 ) ( 7 11 ) ( 8 12 ) , ( 1 14 ) ( 5 10 ) ( 3 16 ) ( 2 9 ) ( 6 13 ) ( 4 11 ) ( 7 12 ) ( 8 15 ) , ( 1 15 ) ( 5 11 ) ( 3 9 ) ( 2 16 ) ( 6 12 ) ( 4 10 ) ( 7 13 ) ( 8 14 ) , ( 1 16 ) ( 5 12 ) ( 3 10 ) ( 2 15 ) ( 6 11 ) ( 4 9 ) ( 7 14 ) ( 8 13 ) }

因为H在 Ω 上正则且 x 2 N X ( P ) H x 2 = P , a x 2 Ω 也是正则的,由上面的叙述可知 a x 2 M ,从而 M x 2 = M 。不失一般性,设 a = ( 1 9 ) ( 5 13 ) ( 3 11 ) ( 2 10 ) ( 6 14 ) ( 4 12 ) ( 7 15 ) ( 8 16 ) ,将其余元素分别记为 n 1 , n 2 , n 3 , n 4 , n 5 , n 6 , n 7 。因此 M = { a , n 1 , n 2 , n 3 , n 4 , n 5 , n 6 , n 7 } 。然而,通过计算, n 1 , b , c , d ( ( Z 4 × Z 4 ) : Z 2 ) : Z 2 n 2 , b , c , d Z 2 × D 8 n 3 , b , c , d ( ( Z 4 × Z 4 ) : Z 2 ) : Z 2 n 5 , b , c , d Z 2 × D 8 n 6 , b , c , d Z 2 × D 8 n 7 , b , c , d Z 2 × D 8 n 4 , b , c , d Z 2 × Z 2 × Z 2 × Z 2 a , b , c , d 。所以只有a和 n 4 满足条件。注意到 n 4 = a b ,则 H x 2 = P , a x 2 = P , a P , a b = a , b , c , d ,从而 H X ,这矛盾于H在X中是无核的。即完成了定理3.1的证明。

基金项目

国家自然科学基金项目(12061089,11701503);云南省科技厅面上项目(2018FB003)。

NOTES

*通讯作者。

文章引用: 李婉婷 , 凌 波 (2021) 3度非弧传递无核Cayley图。 理论数学, 11, 1747-1751. doi: 10.12677/PM.2021.1110196

参考文献

[1] 徐明曜. 有限群导引(上、下册) [M]. 第二版. 北京: 科学出版社, 1999.

[2] Li, J.J. and Lu, Z.P. (2009) Cubic s-Arc Transitive Cayley Graphs. Discrete Mathematics, 309, 6014-6025.
https://doi.org/10.1016/j.disc.2009.05.002

[3] Lorimer, P. (1984) Vertex-Transitive Graphs: Symmetric Graphs of Prime Valency. Journal of Graph Theory, 8, 55-68.
https://doi.org/10.1002/jgt.3190080107

[4] Sabidussi, G. (1964) Vertex-Transitive Graphs. Monatshefte für Mathematik, 68, 426-438.
https://doi.org/10.1007/BF01304186

[5] Bosma, W., Cannon, C. 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

[6] GAP, The GAP Group and GAP-Groups (2002) Algorithms, and Programming. Version 4.3.

分享
Top