（基础数学专业论文）半二面体群的小度数cayley图.pdf

摘要 群g 的一个c a y l e y 图x = c a y ( g ，s ) 称为正规的，如果右乘变换群r ( g ) 在 a u t x 中正规本文研究了4 m 阶半二面体群g = ( ，6n 2 ”= 6 2 = 1 ，驴= n 一1 ) 的3 度和4 度c a y l e y 图的正规性，这里m = 2 ，且r 2 ，并得到了几类非正规 的c a y l e y 图 关键词：c a y l e y 图正规c a y l e y 图半二面体群 a b s t r a c t ac a y k yg r a p hx = c a y ( g ，s ) o fg m u pgi ss a i dt ob en o r m 8 1i fr ( g ) ，t h eg r o u p o fr i 曲t m l t i p l i c a t j o n s ，i sn o m a li na u t x i nt h i sp a p e r ，b yi 删t i g a t i n gt h en o m a l i t y l w ec l a s s 由3 一v m e n ta n d 垂v m e n tc a y l e yg r a p h so fs e m i - d i h e d r a lg r o u p so fo r d e r4 m ，g = ( g ，6l 2 m = 6 2 = 1 ，n 6 = 扩一1 ) ，w h e r em = 2 7 ，r 2 i na d d i t i o nw eo b t a i ns e v e r a l i 瓶n i t ef 锄i l i e so fn o n n o r m 甜c a y l e yg r 印h so fs e m i d i h e d r a lg r o u p s k e yw b r d s ： c 8 y l e yg r 印hn o r m a lc a y l e yg r a p h 8 哪i d i h e d r a lg r o u p 2 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者( 签名) ：瑚西* l 二零零六年五月 日 引言 在本篇文章中，若没有特别声明，所指的图均为有限、无向、简单的连通 图，对于群论中的概念和记号，这里不再定义，请参考 2 ，3 ，4 ，5 】 给定一个图x ，我们用v 瞵) ，e ( x ) 和a = a u t ) 分别表示图x 的顶点 集，边集和全自同构群对于两个顶点和 ，我们用“一”表示相邻，用h ” 表示连接u 和”的边，用( u ， ) 表示从“到”的弧，用蜀( ”) 表示”的邻点集 合，五( u ) 表示与”距离是i 的点的集合 令g 是一个有限群，s 为g 的不包含单位元1 的子集，我们如下定义群 g 关于其子集s 的c a 啦e y 有向图x = c a y ( g ，s ) ：顶点集为v ( x ) = g ，边集为 日暖) = ( 9 ，s 9 ) b g ，s 耐c 8 y l e y 图c 8 y ( g ，s ) 叫做正规的，如果r ( g ) 里a = a u t ( x ) 一个有限群g 有正规的c a y l e y 图，如果g 有子集s 使得群g 关于子 集s 的c a y l e y 图x = c a y ( g ，s ) 是正规的 c a y l e y 图由a c a y l e y 在1 8 7 8 年提出的，当时是为了解释群的生成元和定义 关系但由于它构造的简单性、高度的对称性和品种的多样性，越来越受到图 论学者的重视，成为代数图论中群与图方向的一个重要研究领域近2 0 年来， 由于计算机的发展，人们发现c a y l e y 图还是构造与设计互联网的很好的数学原 型，因而又获得了实际的应用，它的重要性日益增加研究c a y l e y 图的正规性 成为群的g r r 表示之外的另一种c a y i e y 图的分类方法近几年来，大量学者 在c a y l e y 图的正规性方面作了许多重要的工作在文献【6 ，7 ，8 ，2 0 】中，作者分别 确定了素数阶循环群、阶为两个不同奇素数的群、2 p ( p 为素数) 阶群的e a y l e y 图的正规性以及所有z 护( p 为素数) 阶群的4 度1 一正则c a e y 图的正规性所 有? = j 。( p 为奇素数) 阶群的4 度连通c a y l e y 图、非交换单群上3 度连通边传递图 和大多数非交换单群上3 度连通图都是正规的( 1 0 ，1 1 ，2 1 】) ；线性群p s l ( 2 ，口) 上 所有连通2 度c a y i e y 有向图、交换群上大多数连通小度数c a y l e y 图和具有两个 幂零类的p 群( p 为素数) 上所有连通4 度c a y l e y 图也都是正规的( 【1 2 ，1 4 ，1 5 ，1 6 】) 在文献【9 ，1 3 ，1 7 ，1 8 ，1 9 】中，作者确定了所有不连通的正规c a y l e y 图、二面体群所 有非正规的4 度1 一正则c a y l e y 图、劬z ( p 为素数) 阶群的所有2 度、3 度非正 规c a y l e y 有向图以及正则p 群上2 度连通非正规c a y l e y 图的分类本文中， 我们研究了所有4 m 阶半二面体群3 度和4 度c a y l e y 图的正规性，这里m = 2 7 且r 2 ，得到了以下结果： 定理l 设x = c a y ( g ，s ) 是群g 关于子集s 的3 度c a y l e y 图， g = ( o ，6n z m = 6 2 = 1 ，驴= 扩一1 ) ，且m = 2 7 ，r 2 ，则x 同构于下列图之一： ( 1 ) c a y ( g ，岛) ，其中s l = n ，o ，6 ) 此时x 是g 的正规c a y l e y 图，且a 1 型易 ( 1 ) c a y ( g ，岛) ，其中岛= 6 ，n ”+ 1 6 ，味此时x 是g 的非正规c a y l e y 图 定理2 设x = c a y ( g ，s ) 是群g 关于子集s 的4 度c a y l e y 图， g ：( a ，6io 。m ：铲：1 ，扩= n 一1 ) ，且m = 2 r ，r 2 ，则x 同构于下列图之一： ( 1 ) c a y ( g ，岛) ，其中岛= n ，o ，6 ，扩) 此时x 是g 的正规c a y l e y 图，且 a 1 裂易 ( 2 ) c a y ( g ，& ) ，其中& = n ) ，酽6 ，o + 协) ， 为奇数且t 易。此时x 是g 的正规c a y l e y 图，且a ，竺霹 ( 3 ) c a y ( g ，岛) ，其中= 0 6 ，o m + 1 6 ，6 ，扩) 此时x 是g 的非正规c a y l e y 图 ( 4 ) c a y ( g ，& ) ，其中民= 0 6 ，血“+ 1 b ，6 ，扩味为偶数且磊。，七2 ( m o d m ) - 此时x 是g 的非正规c a y l e y 图 ( 5 ) c a y ( g ，岛) ，其中岛= ，n ，6 ，n ) ，k 为偶数且七邑。 当女土2 ( m o d m ) 时，x 是g 的正规c a y l e y 图，且a l 兰面； 、当七；士2 ( m o d m ) 时，x 是g 的非正规c ”l e y 图 2 预备知识 定义1 1 1 设g 是有限群，s 为g 的不包含单位元1 的子集，我们如下定 义群g 关于其子集s 的c a y l e y ( 有向) 图x = c a y ( g ，s ) ： y ( x ) = g ， e ( x ) = ( 目，s g ) l g g ，s s ) 定义1 2c a y l e y 图c a y ( g ，s ) 叫做正规的，如果r ( g ) 笪a = a u t ) 有限群 g 说有正规的c a y l e y 图，如果g 有子集s 使得群g 关于子集s 的c a y l e y 图 x = c a y ( g ，s ) 是正规的 定义1 3 设g 是有限群，称( 无向) 图x 为g 的图正则表示( g r r ) ，如果x 的自同构群a u t x 同构于g ，并且在y ( x ) 上作用正则 c a y l e y 图是一类重要的点传递图，关于c a y l e y 图有以下基本事实： 命题1 ( x = c a y ( g ，s ) 是群g 关于子集s 的c a y l e y ( 有向) 图，则 ( 1 ) a u t ( x ) 包含g 的右正则表示r ( g ) ，因而x 是点传递的 ( 2 ) x ( 作为有向图) 连通当且仅当x 强连通，当且仅当g = ( s ) ( 3 ) x 是无向图当且仅当s _ 1 = s ，这里我们把一条无向边 u ，”) 等同于两条 有向边( u ，”) 和( ”，u ) 命题2 ( 3 】) 设a u t ( g ，s ) = n a u t ( g ) is 。= s ，则有 ( 1 ) j ( r ( g ) ) = 咒( g ) a u t ( g ，s ) ； ( 2 ) a = r ( g ) a u t ( g ，s ) 等价于r ( g ) 里a 命题3 ( 3 | ) 设x = c a y ( g ，司是群g 关于子集s 的c a y l e y ( 有向) 图，设a 1 是单位元l 在a 中的点稳定子群，则x 正规当且仅当a 。的每个元素都是群g 的自同构 命题4 ( 【1 1 】) 设x = c a y ( g ，s ) 是群g 关于子集s 的c a y l e y 图，x 是正规 的，若以下条件成立： ( 1 ) v 妒a 1 ，p l s = 1 s ，贝0 有妒i s 。= 1 s 2 ，即妒= 1 g ； ( 2 ) 坳a 1 ，则存在盯a u t g ，使得妒i s = 口1 s 3 定义半二面体群g = o ，6 1 n 2 ”= 6 2 = 1 ，0 6 = 扩- 1 ) ，此处m 为大于2 的偶数 根据群g 中元的共轭作用考虑群g 中元的阶：o ( 一) = 2 m ，( i ，2 m ) = 1 ； 。( 6 ) = 2 ， 为偶数；o ( 6 ) = 4 ，i 为奇数 考虑g 的中心：z ( g ) = ( 扩) ，当4 不整除m 时；z ( g ) = 如等) ，当4 整除m 时 考虑g 的换位子群：g ，= ( 鲥ig 。g ，啦g ) = ( 0 2 ) 在参考文献 1 中，作者确定了广义四元数群的全自同构群，下面我们用 类似的方法来考虑半二面体群g 的全自同构群，从而确定群g 的所有3 度和 4 度c a y l e y 图x = c a y ( g ，s ) 中的s 考虑a u t g 的阶： 考虑a u t g 中元的形式，对于妒a u t g ，则l p 有以下形式，妒：o 一矿，6 一 o 。4 b ，( i ，2 m ) = 1 因此 有( 2 m ) 种选择，f 有m 种选择，故ja u t gj ( 2 m ) m ； 另外对于任意的妒：n 一，6 一n 2 2 6 ，( i ，2 m ) = 1 均为a u t g 中的元，因此ia u t gi = 咖( 2 m ) m 我们有以下结论： 引理1 1 ( 4 】) 设p 为素数，n 1 ，则 ( 1 ) 当p 2 时，a u t ( z 矿) 兰磊一( p 一1 ) ； ( 2 ) 当p = 2 时，a u t ( z 2 ) = 1 ；当n 2 时，a u t ( z 2 n ) 垡易易n 一。； ( 3 ) 设礼可素分解为n = 疗膂砖，其中鼽为互不相同的素数，则a u t 磊兰 嗡- t 一凳 引理1 2 设群g = ( n ，6fn 2 ”1 = 6 2 = l ，驴= 0 2 1 ，此处m 为大于1 的数， 则a u t g 竺邑m ：( 磊易一，) 证明由于 a u t g = ( 2 m 十1 ) 2 ”，用群的扩张理论确定g 的全岛同构群的 结构由群的定义构造g 的自同构：n ：n 一。，6 一0 2 6 ，因为p = 2 ，m 1 ，故 z 函+ ，垡易历。一由茹。，的结构知缉。+ 。中没有2 “阶元，所以需要构造两 个元：口：o o a ，6 6 ；，y ：口一o r l 6 6 ，其中s 是易m 的2 1 阶元，因此 s = 5 + 2 m 十，r = 1 + 2 m ，r 不包含在( s ) 中，则有d ( o ) = 2 ，o ( 卢) = 2 1 ，d ( 7 ) = 2 ， 4 且卢。：o n ，b 一6 ，t 为s 在z 刍。+ 。中的逆元，又有( 卢) n ( ，y ) = 1 且( p ) ，( ，y ) 可交换由于g 的自同构为妒：n 一，6 一n 2 6 ，( i ，2 m ) = 1 ，f z 2 。，故( 。) 是 g 的特征子群，因此咖a u t g 都导出一个( n ) 的自同构= 妒定义映射 + ：a u t g a u t ( 。) ，妒一，易证+ 为同态满射，且同态核为k e r + = 妒a u t gn p = n = ( a ) 里a u t g 由同态基本定理知a u t g ( q ) 竺a u t ( 易。+ - ) ，a u t ( 易。+ - ) 掣( 万，彳) = ( 万) ( 劢又因为( 。) n ( ( 卢，1 ) ) = ( q ) n ( ( 卢) ( ，y ) ) = l ，故下面仅需证( 卢) ，( 7 ) 正规 化( 口) 由于扩“。p = ( 口。) 卵= ( ) 9 = 。“= ，护- 1 。p = ( 6 。) 4 = ( 0 2 6 ) = n 2 s 6 = 铲5 ，故 有卢_ 1 卢= n 5 同理有7 _ 1 0 y = q 因此a u t g 兰磊。：( 忍易。一) 口 引理1 3 设g = ( o ，60 2 ”= 泸= 1 ，0 6 = o ”。) ，m = 2 一p r 2 磅为m 的素数 分解，其中p “p 2 ，m 为素数，且p l p 2 2 s 为g 中不包含单位元的子集，并且满足s = s ，( s ) = g ，则以下结论成立： ( i ) 若s 为g 的3 元子集，则s 在a u t g 下的轨道有两个，其代表元分别 为： s 1 = o ，n 加) = b ，n ”+ 1 6 ，6 ) ( i i ) 若s 为g 的4 元子集，则s 在a u t g 下的轨道有五个，其代表元分别 为： 岛= ，n ，6 ，n ”) & = o ，日，6 ，扩+ 4 味i 为奇数，且i 历。 岛= n 6 ，n “+ 1 b ，6 ，。”) 6 岛= n 6 ，n + 1 6 ，6 ，口 ，七为偶数，且七z 赫 岛= h n ，6 ，o 味七为偶数，且七z 2 m 证明( i ) 3 元子集在a u t g 下的轨道，可分三种情况：s 中只有2 阶元；s 中有2 阶元和4 阶元；s 中有2 阶元和2 m 阶元下面分别讨论： ( 1 ) s 中只有2 阶元 g 中2 阶元有两种形式：0 2 6 ，osf 墨m 一1 ；n m ，因此只有2 阶元的s 生成 ( n 。，6 ) 的子群，所以不能生成整个群g ( 2 ) s 中有2 阶元和4 阶元 g 中4 阶元有两种形式：n 等；一6i 为奇数s 中若有4 阶元。号，则必有 ( o 号) 一- ：n 警，再加上任意一个2 阶元，这样的s 不能生成整个群s 中若有4 阶元n 岫，i 为奇数，则必有( 渤) 。= o “6 ，i 为奇数若s = 6 ，扩十6 ，0 2 6 ) ，其中 i 为奇数时，取盯：n o ，6 一o - 2 1 6 ，显然口a u t g ，则有s 4 = o 6 ，扩“6 ，n 2 j 6 ) 。= o 一* 6 ，n m + 矗，6 ) ，其中i 一七为奇数因此s 只可能有一种情况，即： s = f o 场，n m + 喝，6 ) ，其中i 为奇数 对于此种情况，由于( i ，2 m ) = 1 ，取矿：。一o r l ，6 6 ， 。为i 在易。中的逆 元，显然一a u t g ，有= o 场，o ”+ 1 6 ，6 ) 4 = n b ，a ”+ 1 6 ，味在同构意义下只须考 虑s = f 曲，o “+ 1 6 ，6 ) 即可 ( 3 ) s 中有2 阶元和2 m 阶元 g 中2 m 阶元的形式为o t ，i 为奇数，则s 只可能有一种情况，长p ： s = n 3 ，n ，6 ) 其中( i ，2 m ) = 1 对于此种情况，由于( ，2 m ) = 1 取盯：o 一甜一，6 6 ，一为i 在玩。中的 逆元，显然盯a u t g ，有酽= p ，o ，6 r = n ，b ) 在同构意义下只须考虑 s = f 。，n ，讣即可 ( i i ) 4 元子集在a u t g 下的轨道，可分四种情况：s 中只有2 阶元；s 中有 2 阶元和4 阶元；s 中有2 阶元和2 m 阶元；s 中有4 阶元和2 m 阶元下面 分别讨论： f 1 ) s 中只有2 阶元 7 g 中2 阶元有两种形式：n 2 协，osf 茎仇一1 ；n ”，因此只有2 阶元的s 只能 生成( 0 2 ，6 ) 的子群，所以不能生成整个群 ( 2 ) s 中有2 阶元和4 阶元 g 中4 阶元有两种形式：。t 6 ，i 为奇数；n 警s 中若有4 阶元n 号，则必有 ( n 詈) 一t = n 警，再加上两个2 阶元，这样的s 不能生成整个群s 中若有4 阶元 o 。b ，i 为奇数，则必有( o t 6 ) 。= n m “b ，i 为奇数可分为以下两种情况： ( a ) s = ( o t 6 ，n ”+ 。6 ，6 ，n “) ，其中i 为奇数 ( b ) s = n 6 ，n ”州6 ，6 ，2 ) ，其中 为奇数 对于( a ) 来说，由于( i ，2 m ) = 1 ，取盯：o o r l ，b 一6 ，z _ 1 为i 在玩。中的逆 元，显然o a u t g ，有酽= f 6 ，。+ 。6 ，6 ，n ) 。= 曲，n ”+ 1 6 ，6 ，o ” 在同构意义下 只须考虑= n 6 ，扩“b ，b ，o ”) 即可 对于( b ) 来说，由于( i ，2 m ) = l ，取盯：n a t ，6 6 ，一为i 在而。中的逆 元，显然盯a u t g ，有酽= 6 ，。”+ ，6 ，n 2 ) 4 = n 6 ，n ”+ 1 6 ，6 ，0 2 ”1 6 ) 在同构意 义下只须考虑岛= 曲，n m + 1 6 ，6 ，n 2 即可 ( 3 ) s 中有2 阶元和2 m 阶元 g 中4 阶元的形式为酽，i 为奇数，则s 有以下两种情况，即： ( a ) s = p ，o ，6 ，n m ，其中i 为奇数 ( b ) s = p ，n ，b ，n 副6 ) ，其中i 为奇数 对于( a ) 来说，由于( i ，2 仇) = 1 ，取盯：n 一，6 6 ，i - 1 为 在z 2 。中的逆 元，显然一a u t g ，有酽= n 2 ，n ，6 ，n ) 4 = 8 ，o ，6 ，o “) 在同构意义下只须考 虑s 3 = n ，n ，6 ，n ) 即可 对于( b ) 来说，由于( i ，2 m ) 一1 ，取a ：。一n 。，6 一b ，i 。为在历。中的逆 元，显然盯a u t g ，有酽= p ，o 一，b ，n 2 2 蛆。一 o ，n ，b ，n 2 州1 味在同构意义下只 须考虑蜀= 。，n ，6 ，n 2 f 6 即可 ( 4 ) s 中有4 阶元和2 m 阶元 s 只能有一种情况，即s = f 酽6 ，n m 6 ，n t ，n ) ，其中i ，j 都为奇数 对于此种情况，由于( i ，2 m ) = 1 ，取一：血一0 2 ，6 一b ，i _ 1 为t 在易。中的逆 8 元，显然盯a u t g 有铲= 6 ，扩钾6 ，n ，口一) 4 = - 1 6 ，”押，o ，o 一1 ) 在同构 意义下只须考虑岛= 口，n ，o 哂，。”“6 ) ，i 为奇数，即可 综上可知，引理得证 9 二 主要结果及证明 引理2 1 设x c a y ( g ，品) 是群g 的关于子集s 1 的c a y l e y 图， g = ( o ，6n 2 ”= 6 2 = 1 ，驴= 扩一1 ) ，岛= n ，o ，味此处m = 2 7 ，r 2 ，则 x = c a y ( g ，岛) 是正规的c a y l e y 图，且a 1 竺邑 图l 证明( 1 ) 首先证明v 妒a 1 ，且妒l s ，= 1 趴则有妒= 1 1 0 啦 _ 扩 扩 挑 扩 v 妒a 1 ，且妒i s = 1 s ，则有妒固定点n ，n ，6 及其邻域 1 ，n 2 ，扩1 6 ， 1 ，n ，o m + 1 b ) 1 ，血6 ，口_ 1 6 ) 由图1 所示，因为过点1 ，6 有且仅有一个d 圈( 1 ，o ，n 2 ，n 一2 6 ，o 一6 ，6 ，1 ) ， 所以妒固定这个6 - 圈，因而妒固定点n 2 ，o 。6 又妒固定集合 0 2 ，一1 6 ) ， 0 6 ，o 一- 6 ) ， 所以妒也固定点口一1 6 ，n 6 又因为过点1 ，n ，6 有且仅有个昏圈( 1 ，6 ，曲，n 。6 ，o ， 。，1 ) ，所以妒固定这个6 - 圈，因而妒固定点n 6 ，n 一又妒固定集合 n ，n m + ，6 ) 1 所以妒也固定点o “+ 1 6 此时有妒l 肼= 1 ，即妒= 1 ( 2 ) 其次证v 妒a 1 ，五a u t g ，使得妒l s 。= 口k 即a 1 竺历 如图1 所示，甄( 1 ) 中只有点n ”的邻域全部包含在恐( 1 ) 中，因此v 妒a ， 有妒固定点n ”及其邻域x ，( n ”) = n ”b ，n 一1 ，n ”+ 又因为在n m 的邻域噩( n m ) 中只有点n ”6 有经过点1 的6 _ 圈( 1 ，n ，扩一1 6 ，n ”，n ”+ 1 6 ，o ，1 ) ，且x 1 ( 1 ) = s l ，故妒 固定b 和集合 口，n - 1 ) ，可分以下两种情况讨论： ( i ) 若妒固定6 ，逐点固定集合 n ，n 一1 ) ，则取一= 1 ，显然有妒i 。，= ak ( i i ) 若妒固定6 ，互换。，。，取。： 。1 ，显然。为a u t g 中的元，且有 i 616 妒| s 。= 盯i s 。 综合( 1 ) ( 2 ) ，由命题4 知，x = c a y ( g ，s 1 ) 是正规的c a y l e y 图，且a 1 兰z 2 口 引理2 2 设x = c a y ( g ，岛) 是群g 的关于子集岛的c a y l e y 图， g = ( o ，6l 。“= 6 2 = 1 ，0 6 = o ”1 ) ，岛= n 6 ，o ”+ 1 6 ，6 ，此处m = 2 ”且r 2 ，则 x = c a y ( g ，s 2 ) 是非正规的c a y l e y 图 证明取口= ( 0 6 ，o m + 1 6 ) ( o ，o 一1 ) ，有 蜀( n 6 ) = 1 ，n ”，n 。1 ) ，x l ( o ”+ 1 6 ) = 1 ，“，。”_ 1 ) ， x 1 ( n 。) = n 6 ，n 2 6 ，m + 2 6 ) ，墨( ”1 ) = o ”1 6 ，口2 6 ，n + 2 b ) ， x 1 ( n 6 ) 4 = 1 ，d “，n 一1 ) 4 = 1 ，n ”，“一1 ) = x l ( o “+ 1 6 ) ， x 1 ( n “+ 1 6 ) 4 = 1 ，n ”，n “- 1 ) 4 = 1 ，口”，o - 1 ) = x 1 ( 口6 ) ， 置( o _ ) 9 = n 6 ，n 2 6 ，o m + 2 磅4 = n ”1 6 ，0 2 6 ，o ”2 6 ) = 蜀( n 一1 ) ， x l ( n m - 1 ) 。= 口卅1 6 ，血2 6 ，n m + 2 6 ) 4 = n 6 ，a 2 6 ，o m + 2 6 ) = 蜀( o - 1 ) 因此a 为图同构且仃a 。 n 6 m 一1铲6 图2 下证盯不是群同构假设盯是群同构，显然有一a u t ( g ，s 2 ) ，必有盯固定 1 ，6 ，因此盯固定沁砷一g ，即一= 1 ，矛盾 这样有口a u t ( g ，岛) 2 ，则 x = c a y ( g ，岛) 是正规c a y l e y 图，且a 1 竺z 2 证明( 1 ) 首先证明咖a l ，且妒f 岛= 1 s 3 ，则有妒= 1 v ( p a 1 ，且妒l s 3 = 1 & ，则妒固定点n ，n ，b ，扩及其邻域 1 ，n 2 ，n ”“，o 一1 曲， 1 ，口，o ”，+ 1 b ) ， l ，n 6 ，n _ 1 6 ，扩味( 1 ，n “，n 一1 ，o “b ) 如图3 所示，在n “的邻 域中只有点口6 与凡( 1 ) 的交是空集，故妒固定点n ”6 因为蜀( 8 ”扛) nx z ( n ) = n 一1 6 ) ，x 1 ( n m 6 ) n x l ( 一1 ) = 口”+ 1 味故妒固定点n “- 1 6 ，o ”+ 1 6 又因为x 1 ( o “+ 1 6 ) n 尥( 1 ) = 0 6 ，扩b ) ，故妒固定点n 6 ，又妒固定点6 的邻域蜀( b ) ，故妒也固定点 n 一1 6 因为x 1 ( ) nx 1 ( o ) = 1 ，n “十1 ) ，x 1 ( n ) nx 1 ( d _ 1 ) = 1 ，o 一1 ) ，故妒固定点 n m ，n m “又因为妒固定6 ，口。的邻域，故妒也固定点n 2 ，于是有妒i 船= 1 ， 即妒= 1 ( 2 ) 其次证v 妒a 1 ， 盯a u t g ，使得妒l s 3 = 盯i & ，即a 1 竺忍 如图3 所示，过点1 有且仅有3 个4 - 圈，即；( 1 n m + 1 ，扩，1 ) ，( 1 ，n ，n 一1 ，n “，1 ) ( 1 ，6 ，n m 6 ，n m ，1 ) 这3 个4 一圈都过点。m ，放v 妒以l 有妒固定点n 由( 1 ) 知，若 1 n 2 6 n m 一2 6 ( i ) 若妒固定点6 ，o ”，逐点固定h o 。) ，则取盯= 1 ，显然有妒i = ak ( i i ) 若妒固定点6 ，。，互换。，。，取。： 。_ 。，显然口为a u t g 中的元， l6 6 且有妒f 岛= 仃k 综合( 1 ) ( 2 ) ，由命题4 知，x = c a y ( g ，岛) 是正规c a y l e y 图，且a 。掣易口 引理2 4 设x = c a y ( g ，) 是群g 的关于子集冀的c a y l e y 图， g = ( n ，6 n 2 “= 6 2 = 1 ，驴= o ”一1 ) ，& = h n ，哂，o m + t6 ) 此处m ：2 r 且r 2 、i 为奇数，则x = c a y ( g ，& ) 是正规的c a y l e y 图，且a ，型职 证明( 1 ) 首先证明坳a 。，且妒i 乳：1 s 4 ，则有妒：1 坳_ 1 ，且妒i s 4 = 1 岛，则妒固定点o ，n ，n ，6 ，o m + t 6 及其邻域 1 ，a 2 ，o m + “6 ，h 6 ， 图4 1 4 1 ，o _ ，扩1 6 ，n ”+ 6 ) t 1 ，口m 6 ，n “6 ，扩) ， 1 ，o ”小1 6 ，o ”+ 州6 ，o ”) 如图4 所示，因为 x l ( n ) n 墨6 ) = 1 ，一1 6 ) ，x l ( n ) n 蜀( 。”+ 2 6 ) = 1 ，扩+ “6 ，故妒固定点_ 1 6 ，n + “6 又因为墨( o 一1 ) n 蜀( 酽6 ) = l ，n 州6 ，置( n ) n 五( n “+ 。6 ) = 1 ，o “+ 州6 ，故妒匿定点 十1 6 ，n “+ 件6 因为妒固定点n ，口，n 喝，o ”州6 的邻域，所以妒也固定点n 2 ，n ，扩 于是有妒i s 产1 ，即妒= 1 ( 2 ) 其次证却a 1 ，j 口a u t g ，使得妒i 鱼= 盯i s 4 ，即a 1 垒霹 如图4 所示，由于在强( 1 ) 中只有点n ”“，n 一1 满足：i 而( 茁) n 恐( 1 ) l = 3 因此 v 妒a 。，不妨设妒1 ，有妒固定集合 扩”，n ”一1 ) 又因为五( o ”十1 ) n x l ( n 一1 ) = n ”) ，故 p 固定点o ”由于过点1 ，o ”有且仅有一个4 一圈( 1 ，扩6 ，o “，。m + 。b ，1 ) ，故 妒固定这个4 一圈，进而妒分别固定集合 一6 ，o “+ 吣) ， ，o _ 1 可分以下三种情况 讨论： r， ( i ) 若妒逐点固定集合 6 ，扩“吣，互换。，。一，取盯： n - 。1 ，显然。为 i6 。n “6 a u t g 中的元，且有妒l = 口l ( i i ) 若妒逐点固定集合 。，。一t ) ，互换舶，。m + z b ，取。： 。，显然盯为 【61 q “6 a u t g 中的元，且有妒i = 盯i ( i i i ) 若妒分别互换n ，n 一- 和酽6 ，。m + t 6 ，取盯： 。“1，显然。为a u t g 中 【6 _ ”“6 的元，且有妒i s 4 = 盯k 综合( 1 ) ( 2 ) ，由命题4 知，x = c a y ( g ，& ) 是正规的c a y l e y 图，且a 笺盈口 引理2 5 设x = c a y ( g ，魄) 是群g 的关于子集& 的c a y l e y 图， g = ( ，6n 2 “= 6 2 = 1 ，0 6 = n 一1 ) ，5 j = o b ，o ”+ 1 6 ，n ”，6 ) ，此处m = 2 7 且r 2 ，贝0 x = c a y ( g ，& ) 是非正规的c a y l e y 图 证明取一= ( 曲，n 叶1 b ) ( o ，n 一1 ) ，有 ，x j ( 0 6 ) = 1 ，扩，n “+ 1 6 ，口”。一1 ) ，x j ( n “+ 1 b ) = l ，口”，0 6 ，n 一1 ， 1 5 n 6 n 一1铲6 n m 一2 夕：亡 司i 眵：6 舞j 习亡x q 图5 墨( n - 1 ) = 扩_ 。，o ”+ 1 6 ，0 2 6 ，扩+ 2 6 ，置( n 一1 ) = o ，0 6 ，d 2 6 ，n 饥+ 2 6 ， x j ( d 6 ) 9 = 1 ，o ，o + 1 6 ，n ”一1 ) 4 ：= l ，o ”，0 6 ，o 一1 ) = x l ( n “+ 1 6 ) ， 两( ”+ 1 b ，= 1 ，o ”，0 6 ，o 一1 ) 4 = 1 ，n ”，n “+ 1 6 ，o ”一1 ) = 。x 1 ( n 6 ) ， x 1 ( a 一1 ) 。= o m 一1 ，m + 1 6 ，n 2 6 ，n m + 2 6 ) 4 = n 一1 ，0 6 ，n 2 b ，n m + 2 6 ) = x 1 ( o m 一1 ) ， 墨( n m - 1 ) 9 = n ，0 6 ，n 2 6 ，n m + 2 6 ) 。= n m _ 1 ，n m + 1 6 ，。2 6 ，n m + 2 吣= 托( o 以) 因此盯为图同构且盯a ， 下证盯不是群同构假设盯是群同构，显然有盯a u t ( g ，) ，必有矿固定 点n ，6 ，因此一固定n ，6 ) = g ，即一= 1 ，矛盾 这样有盯a u t ( g ，鼠) 2 ，为 偶数且z 。，土2 ( m o d m ) ，警( m o d m ) ，m ，等2 ，则x = c a y ( g ，岛) 是非正规 的c a y i e y 图 证明v 妒a 1 ，且妒i = 1 s 6 ，则妒固定点曲，n ”+ 1 6 ，扩6 1 6 及其邻域 1 ，o ”，o 一1 ， m + ， 1 ，扩，o ，一1 ) ， 1 ，n ，o “一，一+ 1 ) ， l ，n ”，口，口扣1 ) 如图6 所示，因为 x 。( 曲) n 蜀( 扩+ 1 砷= 1 ) o ) ，故妒固定点o ”，进而固定集合 口6 ，扩+ 又因为 1 6 图6 1 7 五( n m 6 ) nx l ( 6 ) = n ，n + 1 ) ，墨( 0 m + 6 ) n 置( o 6 ) = 。一，口“十1 ) ，又妒分别固 定n “6 ，6 的邻域x 。( 咄6 ) ，五( 6 ) ，故妒固定点矿，n 因为| 噩( o 。) n 蜀( n m + 卜1 ) i = 1 ，1x l ( o 。) nx 1 ( 扩- 1 ) 1 = o ，故妒固定点扩，扩+ 卜1 又lx 1 ( 0 2 ) nx l ( n b l ) 卜1 ，l x ，( 扩) n x 。( n - 1 ) i = o ，故妒固定点矿，o 若妒f 礤1 霹，则必有妒l = ( n ，o “+ 1 ) ( n 一2 ，n 。) 由于e a y l e y 图是点传 递的，故若妒固定点。且逐点固定。的邻域，则妒变换点，n ”“z 由图6 可 知，【p 固定点驴，且逐点固定扩的邻域，因此妒变换点n 1 + ，扩“，进而变换 点a 1 十* ，扩“下分两种情况讨论： ( 1 ) 若( 女) = ( 2 ) 时，由于( 七) = ( 2 ) ，故存在整数t 使得1 + 舰= 一1 ，又妒变换 点n t ，扩“州，即变换点n ，扩，由前面证明可知妒固定点n ，o 一，矛盾 因此若( 七) = ( 2 ) 时，坳a 1 ，且妒i 岛= 1 & ，则有妒= 1 下证当( 七) = ( 2 ) 时，x = c a y ( g ，岛) 是非正规的 这时取口：一一m ，6 一n 6 显然口为a u t g 中的元，取f 兄( n ) 一r ( n ) 口 r ( 6 ) 一r ( 6 ) 盯 口_ 口 容易验证r 是图同构且丁a 1 ，显然r 不是群同构，此时有a u t ( g ，s 6 ) a t 所 以当( ) = ( 2 ) 时，x = c a y ( g ，& ) 是非正规的 ( 2 ) 若( ) ( 2 ) 时，即( ) ( 4 ) ，不妨设：4 s ，取，：n l 。 一 。5o ，3 ( m 。d 4 ) 【o m + 4 ，f5l ，2 ( m o d 4 ) r 。z 6 。2 6 ， k o ，1 ( m 。d 4 ) 显然，不是群同构下面验证r 是图同构，即验 in “6 ，f _ 2 ，3 ( m o d 4 ) 证x 中的任意点扩，6 在r 作用下保持边的邻接关系，下面具体验证点在r 作用下保持边的邻接关系： 当i ；o ( m o d 4 ) 时，有x l ( 。4 ) = o 一2 6 ，o 一件4 8 6 ，n 一4 + 1 6 ，n 一4 + ”+ 1 6 ) ， x j ( ( 0 4 ) 7 ) = 口一。6 ，n 一件4 5 6 ，n 一计1 6 ，n 一+ ”+ 1 6 = x i ( ) 当馆l ( m o d 4 ) 时，有置( 酽) = 护。6 ，n 一州5 6 ，n 1 + 1 6 ，d 一”+ 1 6 ) x 1 ( ( n 。) 7 ) = 一。6 ，o 一+ 4 5 6 ，。一什1 6 ，一种”+ 1 6 ) = x t ( n ) 1 8 当拒2 ( m o d 4 ) 时，有蜀) = 如1 6 ，0 1 伸6 ，n 1 + 1 6 ，0 1 + 斛1 6 ， 置( ( ) 7 ) = 扩。6 ，扩。柏6 ，o q 十1 b ，n 一十耐1 b ) = 研( 。2 ) 当ii3 ( m o d 4 ) 时，有墨( 酽) = n 一b ，n ”件4 ，0 1 “6 ，o 一十m “b ) ， x 1 ( ( o ) 7 ) = o ”一。b ，”一件4 5 b ，n 一4 十1 6 ，o 一件“+ 1 6 ) = x i ( 矿) 同理可证点n 强在r 作用下也保持边的邻接关系故r 是图同构且r 4 ，此时 有a u t ( g ，品) a 1 所以( 七) ( 2 ) 时，x = c a y ( g ，岛) 是非正规的 综合( 1 ) ( 2 ) ，引理得证 关于引理2 6 的特殊情形 引理2 6 要求七土2 ( m o d m ) ，罟( m o d m ) ，m ，璺# ，是要保证图6 中无重点， 下面具体考虑七= 2 ，m ，m + 2 的情况： 情形1x = c a y ( g ，s ) 是正规的c a y l e y 图，其中s = 曲，口“+ 1 玩n 2 6 】6 ) 证明( 1 ) 首先证明v 妒a ，且妒l s = 1 s ，则有_ p = 1 a 1 ，且妒 s = l s ，则妒固定点n 6 ，口”+ 1 6 ，。2 ，6 及其邻域 1 ，n ”，n 一1 ，扩+ 1 ) ， 1 ，o m ，n ，n ， 1 ，n 一，一1 ，一1 ) ， 1 ，”，2 ) 如图7 所示，因为五( n 6 ) n 噩( o ”+ 1 6 ) = 1 ，n m ) ，x 1 ( n 6 ) n 托( 6 ) = 1 ，n ”+ 1 ) 故妒固定点o “，n “州，n 又因为函( 6 ) n x 1 ( 扩+ 1 6 ) = 1 ，o ) ，x 1 ( 护6 ) n 五( 。”+ 1 6 ) = 1 ，o 一1 ) ，故妒固定点n ，o ，0 2 ，n 于是 有妒i 舻= 1 ，即妒= 1 ( 2 ) 其次证v 妒a l ，j 盯a u t g ，使得妒i s = 口b 如图7 所示，由于在玛( 1 ) 中只有点。”b ，n m + 2 6 满足：i 五( z ) nx 。( 1 ) i = 3 ，故却4 。，不妨设妒1 ，有妒固定集合 n ”6 ，n “+ 2 ”又因为x z ( o ) n x 。( o m + 2 6 ) n ( 1 ) = n ” ，故妒固定点o “由于过点l ，n ”有且仅有一个4 一圈 ( 1 ，曲，n m ，n m + 1 b ，1 ) ，故妒固定这个4 - 圈，进而妒分别固定集合 n 6 ，n ”1 6 ， n 2 6 ，6 可分以下三种情况讨论： ( j ) 若妒逐点固定集合 。2 b ，醯，互换n 6 ，扩+ 1 6 ，取盯： 。4 扩+ 1 ，由于( m + 【6 。6 1 ，2 m ) = 1 ，故仃为a u t g 中的元，且有妒l s = 仃i s 1 9 图7 ( i i ) 若妒逐点固定集合 n b ，扩+ 1 6 ) l 。一n ，显然盯为 l6 _ 2 6 l a u t g 。篙羔纛粕，螈盯忙1 ，蚓一，刎：， ( i i i ) 若妒分别互换曲，扩+ 1 b 和0 2 6 ，6 ，取盯： ，。 ，由十( m 一1 ，2 m j51 故盯为a u t g 中的元，且有妒i s = 盯i s 综合( 1 ) ( 2 ) ，由命题4 知，x = c a y ( g ，s ) 是正规的c a y l e y 图 2 0 情形2x = c a y ( g ，s ) 是非正规的c a y l e y 图，其中s = 曲，扩+ 1 6 ，n ，6 ) 6o m 一1 b 2 6n m 一2 图8 证明取盯= ( 0 6 ，a m + 1 6 ) ，有 置( 0 6 ) = 1 ，n ”，o ，扩_ 1 ) ，噩( o 卅1 6 ) = 1 ，n “，o ，扩q ) ， x j ( n 6 ) 4 = l ，坍，