（运筹学与控制论专业论文）交换群上五度弧传递cayley图.pdf

声明 本人郑重声明：本论文的所有研究工作都是在我的导师一 冯衍全教授指导下，由本人独立完成，论文中所引用的已知结论 均已列在参考文献中未经本人许可，任何擅自更改，抄袭本论 文之内容的行为，都将承担相应的学术和法律责任 目录 摘要 c a y l e y 图由a c a y l e y 在1 8 7 8 年提出的，当时是为了解释群的生成 元和定义关系，由于它构造的简单性、高度的对称性和品种的多样性，越 来越受到图论学者的重视，成为群与图的一个重要的研究领域近二十年 来，由于计算机的发展，人们发现c a y l e y 图还是构造与设计互联网络的 很好的数学模型，因而又获得了实际的应用，它的重要性日益增加 c a y l e y 图x = c a y ( g ，s ) 称之为正规的，如果g 的右正则表示矗( g ) 正规于x 的全自同构群a u t 僻) 有关c a y l e y 图正规性的研究也是刚刚 起步，它是由北京大学徐明曜教授在1 9 9 8 年提出的，正式发表于1 9 9 8 年d 担c 他t em 口t h e m o 缸c s 的a u t o m o r p h i s mg r o u p sa n di s o m o r p h i s m so f c a y l e yd i g r a p h s ( 8 】一文中 c a y l e y 图正规性对很多方面的研究都有很重要的意义例如t 弧传 递图，c i 一子集和半传递图等，交换群上n 度m 5 ) c a 叭e y 图的正规性 已经全部给出( 6 】， 7 】) ，所以很自然就考虑交换群上c a y l e y 图的弧传递 性最近，徐明曜等对交换群上四度1 一正则e a m e y 图和交换群上度数不 超过四的弧传递c a y l e y 图进行了分类( 4 i 5 】) 在本文中我们主要对交换群上五度弧传递c a 辨y 图进行了分类，并 给出这些弧传递图的自同构群，同时还确定了这些图的s 一传递性在本文 的最后一章，我们还给出了交换群上二度有向c a y l e y 图的弧传递分类 关键词：弧传递图， 传递图，正规c a y l e y 图 a b s t r a c t a c a y l e yc o n s t r u c t e dt h ec a y l e yg r a p hi n1 8 7 8i no r d e rt oe ) ( p i a i t h eg e n e r t i n ge l e m e n t sa n dd e 丘n i t i o nr e l a t i o n 80 fg r o u pa t t h a tt i m e b u t b c c a l 】s eo fi t s8 i m p l m c a t i o no fc o n s t r u c t i o n ，h i g hs y m m e t r ya n dv 缸i e t i e s ， r e s e a r c l l e r so ng r 印ht h e o r yp a y m c ha t t e t i o no ni t c a y l e yg r a p h s h a v eb e c o m ea ni m p o r t 蛆tr e s e a r c h 盆e l do fg r o u p8 n dg r a p h e 8 p e d a l l y i nr e c e n tt w e n t y ”a r s ，讯t ht h ed e v e l 叩m e n to fc o m p u t e r s ，p e o p l e 丘n d t h a tg a y l e yg r a p h sa r eg o o dm a t h e m a t i c 出m o d e l st oc o n s t r u c ta n dd e s i g n i n t e r n e tw o r k s t h u s ，i tg e t sp r a c t i c a la p p l i c a t i o na 皿db e c o m e sm o r ea 1 1 d m o r ei m p o r t a n t f 0 rac a y l e yg r a p hx = c a y ( g ，s ) ，xi 8s a i dt ob cn o r m a li ft h e r i g h tr e g u l 缸r e p r c 8 e n t a t i o nr ( g ) o fg i sn o r m a ii 七h ef i l l la u t o m o r p h i s mg r o u pa u t ( x ) o fx t h es t u d yo ft h en o r m 出i t yo fc 8 y l e yg r a p h s h a sb e e ni n v c s t i g a t e dr e c e n t l 矿i tw a sp r o p o s e db yp r o f e s s o rx ui 1 9 9 8 ， i na u t o m 。r p h i s mg r o u p sa n di s o m o r p h i s m so fc a y l e yd i g r 印h s ，d i s c r e t e m a t h e m a t i c s 1 8 2 ，3 0 9 3 1 9 t h cs t u d yo ft h en o r m m i t yo fc a y l e yg r a p h si si m p o r t a n ti nm 哪瓣 p c c t s ，f o r 既a m p l e ，8 r c - t r a l l s i t i v eg r a p h ，c i s u b s e ta n da n dh 甜f - t r a n s i t i v e g r a p h t h en o m 柏i t yo fc a y l e yg r a p ho 丘i l i t ea b e l i a ng r o u p sw i t hv a _ 1 e n c ya tm o s t5h a sb c e nd o n ei n1 6 1a n df 7 i nt h i sp a p e rw ec o n s i d e rt h e c l a s s i 丘c a t i o no fa r c _ t r a n s i t i v ec a y l e yg r 印h so na b e l i a ng r o u p 8 r e c e n t l y 】 t h ec l 蹦s i 丘c a t i o no fo n e _ r e g u l a rc a y l e yg r a p h so f 砌e n c yf o u ro na b e l i a n g r o u p s8 n d 盯c _ t r a n s i t i v ec a y l e y 铲a p h so fv a | e c ya tm o s “b u ro na b e l i a i l g r o u p sw e r eg i v e ni n 4 a n d 5 i nt h i 8p a p e r ，w 8g i v eac o m p l e t ec l 雒s m c a t i o no f 龃c t r a 8 i t i v eg & y l e y g r a p h so fv a l e n c yf i v eo n 如e l i a n 擎o u 秘a n dd e 泐m i n e t h e i rf u l l 氆u t o m o 卜 p h i 8 mg r o u p 8 ，a l s o 眠d e t e r m i n et h es t r a n s i t i v e s u c hg r 即h sf o rs 2 a n dac o m p l e 钯c l a s 8 碾c 批b no fa r 昏t r 鲥匹i t i v ec 蝌l qd i g r a p h s0 fv 【e n c y t w 0o n8 b e l i a n 廖o u p si s 舀v e ni nt h el 鹤tc h a p t e r k e yw o r d s ：脚p t r a 工1 8 l t g r a p h ，s t r 缸商t i v e 擎a p h ，n o r m a lc a y l e y 舒印h 矿( x ) e ( x ) j 4 f x ) a u t f z l a u t f x l 全文通用记号 有限群 子集 图 顶点集 边集 弧集 自同构群 自同构群 g s x 第一章绪论 1 1 基本概念与结论 为方便起见，本节先介绍本文常用的一些基本概念与结论 一个有限简单图x 是指一个顶点数有限且无环无重边的图，即顶点 集y ) 有限，边集f ( x ) y 2 ：= 牡，u ) iu ，w v u u ) ，通常记作 x = ( k e ) 如果有另一个图x = ( 矿7 ，e 7 ) 满足：存在y 到y 的一个 双射口，使( ，u ) e 甘( 矿，俨) e ，则称口为图x 到图x 7 上的同构 映射，并称图x 与图x 7 同构，记作x 兰x 我们经常讨论的是顶点集相同的两个图的同构问题，即y = y ，这 时图x 与图x 同构当且仅当：存在y 到上的同构映射a ，使得 ( u ，刨) e 车 ( “4 ，u 。) e 特别地，图x 到自身上的同构映射称为x 的自同构而图x 的全体 自同构在置换乘法下构成个群，称为图x 的全自同构群，记作a u t ( x ) 而a u t ( x ) 的子群统称为x 的自同构群 对于一个有限简单图x ，用y ( x ) ，e ( x ) ，a ( x ) 和a u t ( x ) 分别表 示图x 的顶点集合，边集合，弧集合和图的全自同构群如果a u t ( x ) 在y ( x ) ，e ( x ) 或a ( x ) 上作用传递，则x 称为是最传递，边传递或 弧传递的设 y ( x ) ，则与口邻接的顶点集合称为 的邻域，记作 蜀( ”) 对于某个正整数s ，图x 的一个s - 弧是指图x 的s + 1 个有序 点列( 如，u 1 ，) ，满足u 一1 与挑在图x 上是相邻接的( 1 曼 曼s ) 且 u ，l o 件l ( 1sl 3 ，g 的s y l 唧一子群g ，是齐次循环 群，而g 3 是循环群或初等交换群， g 2 是初等交换群或g 2 竺五 ( 4 ) g 是1 一c i - 群当且仅当它的s y l o w 2 一子群g 2 是齐次循环群 ( 5 ) g 是m c i 一群，2 m 5 ，当且仅当g 是2 一d c i 一群，即它的每个 s y l o w 子群是齐次循环群且g 2 是循环群或初等交换群 前面提到c a y l e y 图都是点传递的，但反之不然事实上，可以证明： 第一章绪论 8 命题1 1 4 ( 有向) 图x = ( v e ) 同构于群g 的c a y l e y ( 有向) 图当且仅 当a u t ( x ) 包含一个同构与g 的正则子群 s a b i d u s s i 给出了依然用群来构造的另一种较c a y l e y 图更具有普遍 性的点传递图； 设g 是一个有限群，t 是其子群，d 是若干个形如t d t ( d 隹丁) 的 双陪集的并，满足d - 1 = d 取顶点集合为子群丁在g 中全体右陪集的 集合，边集合e = 功，t 由) lg g ，d d ) ，则图x = ( u e ) 称为g 关于t 和d 的s a b i d u s s i 陪集图记作x = s a b ( g ，t ，d ) 显然x 是连 通的当且仅当( d ) = g 显然g 的右乘传递置换表示兄( g ) a u t ( s a b ( g ，r ，d ) ) ，所以s a b i d u s s i 陪集图也是点传递的 反之，每个点传递图一定是其全自同构群的某个s a b i d u s s i 陪集图 事实上，设x = ( k e ) 是点传递图，取g a u t ( x ) 且g 在x 上点 传递，t = 瓯为g 在顶点u y 上的点稳定子群以及d ：= g gj ，伊) e ) 易知d 是若干个形如功r 0 车t ) 的双陪集的并，且 d - 1 = d 可以证明x 笺s a b ( g ，l d ) ，并且x 是弧传递的当且仅当d 是单个双陪集 下面我们介绍有关正规c a y l e y 图的概念，这对我们研究图的对称性 很有帮助首先我们有： 设x = c a y ( g ，s ) 是g 关于s 的c a y l e y 图，兄( g ) 表示g 的右正 则表示又设 a u t ( g ，s ) = n a u t ( g ) ls 。= s ) 明显有r ( g ) a u t ( g ，s ) a u t ( x ) 令a = a u t ) ，则有 第一章绪论9 命题1 1 5 1 1 ( 1 ) ( r ( g ) ) = r ( g ) xa u t ( g ，s ) i ( 2 ) a = r ( g ) a u t ( g ，s ) 和r ( g ) 司a 等价 下面给出正规c a y l e y 图的定义 定义1 1 6 称c a 姐e y 图x = c a y ( g ，s ) 是正规的，如果g 的右正则表 示r ( g ) 在x 的全自同构群a u t ( x ) 中正规 由命题2 2 1 我们可以得到： 命题1 1 7c a y l e y 图x 正规当且仅当a l = a u t ( g ，s ) ( a = a u t ( x ) ， a 为单位元1 在a 中的稳定化子1 特别地，图x 如果是某个群g 的c a y l e y 图并满足a u t ( g ，s ) = g ， 则称x 是g 的一个图正则表示，简称g r r 对于正规c a y l e y 图的弧传递性，由命题2 2 1 易得 命题1 _ 1 8 设x = c a y ( g ，s ) 是g 的关于s 的正规c a y l e y 图则x 弧传递当且仅当a u t ( g ，s ) 在1 的邻点集合上传递 1 2 研究背景 众所周知，群以它高度的抽象性和广泛的应用性在众多的自然学科 领域中扮演着重要的角色，其中尤以群作用最为活跃而群在图上的作用 则是群作用的一个重要方面，对于这个领域的广泛的研究是在1 9 6 0 年以 后尤其是近三十年来，在这方面出现了很多重要的工作 在群与图的研究中，图的对称性一直是个热门话题它主要是通过图 的自同构群具有某些传递性来描述，因此，这些问题的关键是决定图的全 自同构群，这对于般的图而言是相当困难的即使对于小度数对称图来 第一章绪论 l o 说，譬如4 度，5 度对称图，目前也没有一般的方法去了解它们的全自 同构群而对于3 度对称图，我们比较容易了解它们的全自同构群尽管 如此，有关小度数对称图的研究一直是群与图研究领域中一个比较活跃 的分支 作为小度数对称图的研究起点，3 度对称图半个多世纪以来一直是 备受关注的对象早在1 9 4 7 年，i 、l t t e 在文2 9 ，3 0 1 中给出了下面的基 本命题 命题1 2 1 一个连通3 度对称图一定是s 正则的，其中s 为一个不超过 5 的正整数 此后，大量关于3 度对称图的有意义的工作便不断的涌现出来，见 1 2 ，2 0 ，2 1 】 我们知道在对称图研究中，c a y l e 节图起着重要的作用而e a y l e y 图 的正规性对于图的对称性质的研究是很有帮助的一个很自然的问题是： 对于某个或某类指定的有限群，决定它的或它们的c a y i e y 图是否正规 然而，在多数情形下，这又是一个十分困难的问题事实上目前已经完全 知道其上的c a 叽e y 图的正规性的群仅有素数p 阶循环群( 1 1 】及其印阶 1 3 和p q 口为素数) 阶群【1 5 另外，还有很多工作给出了这个问 题的部分回答例如，文【1 6 确定了所有非连通正规c a y l e y 图文 1 7 】 证明了绝大多数非交换单群上的连通2 度c a y l e y 图是正规的文【1 8 中 证明了线形群p s l ( 2 ，g ) 上的所有连通2 度有向c a y l e y 图是正规的文 1 9 中决定了正则p 群上连通2 度有向c a e y 图的正规性文【6 ，7 ，2 2 】 中证明了有限交换群上的大多数小度数连通c a y l e y 图是正规的，并且幂 零类为2 的p 群( p 为一个奇素数) 上的所有4 度连通c a y l e y 图是正规 的文( 2 3 还给出了所有2 p 2 阶( p 为素数) 连通2 度非正规c a y i e y 有向 第一章绪论 图文 2 4 】中证明了，在同构意的义下，有限非交换单群上仅有两个非正 规的连通弧传递3 度c a y l e y 图，等等 本文的出发点就基于这种思路：利用交换群上c a 叽e y 图的正规性， 决定交换群上弧传递c a y l e y 图的分类关于这个问题，小度数c a y l e y 图 已经有比较丰富的结果譬如， 4 1 给出了4 度1 一正则循环图的完全分 类 f 5 】给出了有限交换群上度数不超过4 的弧传递c a e y 图的完全分 类本文主要对交换群上五度弧传递c a y l e y 图进行了分类，并给出这些 弧传递图的自同构群，同时还确定了这些图的s 一传递性最后对交换群 上二度有向弧传递c a y l e y 图进行了分类 1 3 本文的主要研究工作 本文全文共分三章，内容是如下安排的： 第二章：对交换群上五度弧传递c a y i e y 图进行了分类，并给出这些 弧传递图的自同构群，同时还确定了这些图的s 一传递性 第三章：对交换群上二度有向弧传递c a y l e y 图进行了分类 第二章 交换群上五度弧传递c a y l e y 图 在本章中，我们将对交换群上五度弧传递c a y k y 图进行了分类，并 证明了交换群上的五度c a y l e y 图x ，若x 是弧传递的，则x 同构于创， q 5 ，坞，5 ，甄或者甄e 一6 尥同时我们给出这些弧传递图的自同构群， 并确定了这些图的s 一传递性 2 1 引言及预备知识 首先我们给出下面要用到的几个图的概念 定义图x 的补图x 的点集为y ( x ) = y ( x ) ，边集为e ( 又) = “u ， ) f “，u y ( x ) ， u ，u ) 甓e 僻) ) 下面我们来定义两个图的笛卡儿 积和字典式积设x 和y 是任意两个图，规定x 和y 的笛卡儿积x y 为具有顶点集合y ( x ) y ( y ) 的图，满足u = ( z - ，t ) 和u = ( 。：，。) 相 邻当且仅当z 1 = 2 且 g l ，2 ) 层( y ) ，或者玑= 抛且( 。l ，。2 ) e ( x ) ( 注：对任意的z - ，。z y ( x ) ，z l 和z 2 相邻是指 z - ，z z e ( x ) ) 规 定x 和y 的字典式积x y 为具有顶点集合y ( x ) y ( y ) 的图，满足 u = ( 。l ，1 ) 和u = ( 。2 ，抛) 相邻当且仅当 z 1 ，0 2 ) e ( x ) ，或者z l = z 2 且 1 ，2 ) e ( y ) 设y ( y ) = 1 ，2 ，) 则在x y 】中有一自然嵌 入n x ，其中第 ( 1 isn ) 个x 是由x y 】中的点 ( z ，玑) i 。y ( x ) ) 诱导出的子图规定删除字典式积x 【y 】一扎x 是由去掉x y 1 中自然嵌 入n x 所有边得到的图 设q 是图x 的点集y ( x ) 上的置换，g ；= ( o ，1 ，n 一1 ) 为长n 第二章交换群上五度弧传递哪j e y 图 1 3 的圈，其中对任意 磊有( i ，。+ 1 ) e ( g ) 规定x 与g 关于a 的 扭圈积x 。的点集和边集如下t y ( x 。g ：) = y ( x ) y ( c i ) = ( z ，z ) lz y ( x ) ，i = o ，1 ，n 一1 ； e ( x 。c ) = “( 。，i ) ，( 。， + 1 ) ) iz y ( x ) ， = o ，1 ，礼一2 u “( z ，n 一1 ) ，( 。，o ) ) iz 矿( y ) ) u ( z ，i ) ，( ，i ) ) ( z ，1 ) e ( x ) ，i = o ，l ，n 一1 ) 剑表示连接4 维立方体矾中的“对角线”得到的图，即连接q t 中 所有距离为4 的点得到的图，。与g 扭圈积，。g 中的c 是 完全二部图。上的一个置换。它循环置换该二部图的每一部分 3 维立方。3 与g 的扭圈积醌d g 中的d 对换q 3 中所有对角线上的 两个点规定图喙 2 尬 的点集为y ( 2 甄 ) = y ( q 。【2 七- ) ，边集为 e ( c 2 坼 ) = e ( ( 乃m 2 j t 】) u ( 。，玑) ，( z i + m ，虮) ) ii = o ，1 ，m l ，j = l ，2 其中y ( g ；m ) = 髫o ，。l ，z 2 m 一1 ) ，y ( 2 k 1 ) = 筝“协 关于交换群上五度c a y i e y 图的正规性有下面的命题 命题2 1 1 【6 】设x = c a y ( g ，s ) 是g 的关于s 的连通正规五度c a y l e y 图，则x 除去以下几种情况都是正规的： ( 1 ) g = 霹= ( 。) 6 ) c ) ( d ) ，s = o ，b ，c ，d ，n 6 c ) ，x = 凰确4 j ( 2 ) g = 缸霉= ( o ) ( 6 ) ( c ) ，s = o ，口，0 2 ，6 ，c ) ，x = q 心i ( 3 ) g = 五霉= ( n ) ( 6 ) ( c ) ，s = n ，o ，6 ，c ，护吣，x = 鲍凰，a j ( 4 ) g = 五z i = ( o ) ( 6 ) ( c ) ( d ) ，s = o ，口一1 ，6 ，c ，d ) ，x = 爿j q 4 = 哦i ( 5 ) g = z 6 露= ( n ) ( 6 ) c ) ，s = 口，n ，扩1 6 ，c ) ，x = 玛，3 q i 第二章交换群上五度弧传递脚f e y 图 ( 6 ) ( 7 ) 8 ) 9 ) o ) 1 ) ( 1 2 ) 3 ) 4 ) 5 ) 6 ) 7 ) g = z m z ；= o ) 砷( c ) ， z 3 ，s = 。，凸一1 ，o b ，n 一1 6 ，c ) ，x = 玛g 2 k 1 】i g = 互m 邑= ( 口) ( 6 ) ，m 3 ，s = 。，n 一1 ，0 2 m + 1 0 2 m 一1 ，6 ) ，x = 尥圆。 2 甄 i g = z l o = ( n ) ，s = n 2 ，一，0 6 ，0 8 ，n 5 ) ，y = 娲x 甄j g = z l o z 2 = ( 。) ( 6 ) ，s = n ，。一1 ，护，n 7 ，6 ) ，x = 岛( k 5 ，5 5 如) ； g = z m 五= ( n ) ( b ) ，m 3 ，s = o ，d 一1 ，6 ，6 1 ，6 2 ) ，x = c k 爿i i g = z 。磊= ( 口) ( 砷，m 3 ，s = 口，n 一1 ，6 ，6 1 ，6 3 ) ，x = ( k 玛3 i g = z 。磊易= ( 口) ( 6 ) ( c ) ，m 3 ，s = 。，。，6 加，c ) ，x = 醌i g = 刃= ( n ) x ( 6 ) ( c ) ，s = o ，6 ，c ，n 6 ，n c ) ，x = 娲( 2 恐 g = z 4 z 2 = ( n ) ( 6 ) ，s = 。，口加，扩，。2 b ) ，x = 鲍【2 娲 i g = z 4 z ；= ( o ) ( 6 ) ( c ) ，s = 口，口一1 ，6 ，c ，2 6 c ) ，x = 0 2 i g = 毛。= ( o ) ，m 3 ，s = ( o ，n 一1 ，n “+ 1 ，o ”1 ，o ” ，x = 0 击 k 胡j g = 磊m z 2 = ( a ) ( 6 ) ，7 n 2 ，s = n ，。一1 ，0 6 ，。一1 6 ，6 ) ，芹= c 娲1 i g = 邑饥z 2 = ( 口) ( 6 ) ，m 2 ，s = 。，。一1 ，a b ，8 1 五，o m ，x = g 2 风】j g = z l o = ( n ) ，s = h 口3 ，0 7 ，n 9 ，0 5 ) ，x = 蚝5 j g = 磊易= ( ) ( 6 ) ，s = o ，n ，0 2 6 ，a _ 2 6 ，6 ) ，x = 甄6 6 i g = 邑。邑= ( o ) ( 酗，m 2 ，s = 。，n ，6 ，6 ，口”6 2 ) ，x = 0 3 。d 瓯i g = 磊。= ( o ) ，m 3 且为奇数，s = 口2 ，o ，o “，o ”，0 3 ”) ，x = 第二章交换群上五度弧传递脚f e y 图 1 5 娲，3 。c k i ( 2 3 ) g = 磊。玩= ( a ) ( 6 ) ，m 2 ，s = o ，。，k ”，6 0 一”，k 3 ) ，x = k 3 ，3x 。倪。 交换群上五度c a y l e y 图正规性的给出，使我们可以考虑其对称性即 弧传递性 2 2 主要定理及其证明 定理2 2 1 设g 是一交换群，x = c a y ( g ，s ) 是g 的关于s 的五度连 通c a y l e y 图，其中s = s 若x 是弧传递的，则x 同构于q 2 ，国5 ， 蚝5 ，甄或者k 6 ，6 6 k 2 在群g 同构的意义下，g 和s 为下列情彤 之一5 ( 1 ) g = 霹= ( n ) ( 6 ) ( c ) ( d ) ，s = n ，6 ，c ，d ，n 抛田，x 型0 ：， a u t ( x ) = z xs 5 ，x 是2 - 传递的 ( 2 ) g = z i = ( 口) 6 ) ( c ) ( d ) ( e ) ，s = n ，6 ，c ，d ，e ) ，x ；! 印5 ， a u t ( x ) = 罐x ，x 是2 传递的 ( 3 ) g = z 4xz i = ( 。) ( b ) ( c ) ( d ) ，s = k ，a ，6 ，c ，nx = 坞q 4 = q 5 ，a u t ( x ) = 动，x 是2 一传递的 ( 4 ) g = 五刃= ( 。) x ( 6 ) ( c ) ，s = o ，o ，6 ，c ，扩6 c ) ，x = q 2 ， a u t ( x ) = 霹s 5 ，x 是2 一传递的 ( 5 )g = z l o = ( o ) ，s = o ，n 3 ，n 7 ，0 9 ，。5 ) ，x = 风，5 ，a u t ( 。x ) = ( 民 品) x 易，x 是3 传递的 ( 6 ) g = 磊z 2 = ( o ) ( 砷，s = 口，舻扫，口- 2 b ，b ，x = 凰，6 6 j f 2 ， a u t ( x ) = 品邑，x 是2 一传递的 第二章交换群上五度弧传递g a y j e ) ，图 1 6 ( 7 ) g = z j z 4 z 2 = ( 口) ( b ) ( c ) ，s = ，n 一1 ，b ，b 一1 ，c ) ，x 釜q 5 ， a u t ( x ) = 劭x 岛，x 是2 传递的 ( 8 ) g = 磊= ( n ) ，s = ，。2 ，。3 ，0 4 ，n 5 ，x 型砥，a u t ( x ) = 岛，x 是 2 一传递的 ( 9 ) g = 五z 4 = ( 。) ( 6 ) ，s = ，o 一1 ，6 ，6 ，n 2 铲) ，x 型0 2 ，a u t ( x ) = 罐w & ，x 是2 - 传递的 证明证明将分x 是正规、非正规两种情况 首先设x 是正规的由于俐= 5 且s = s ，所以s 至少含有一 个2 阶元又由x 的正规性得到a u t ( g ，s ) 在s 上作用传递，所以s 中 所有元素均为2 阶元因此g 只有三种情况：g = 翟，霹，或霹 ig = z i = ( n ) ( 砷( c ) 考虑x 的补图叉明显，a u t ) = a u t ( x ) ，由于l g l = 8 ，叉度数 是2 由于c a y l e y 图是点传递性的，x 的每一个连通分支都是a u t ) 的非本原块因此叉只有两种情况：x = 国或2 q 若x = g ，则a u t ( ：哪) = d 1 6 ，阶为1 6 的二面体群因为a u t ( x ) 中 没有5 阶元，x 一定非弧传递若x = 2 q ，则a u t ( x ) = ( d 8 d 8 ) z 2 同理可得x 非弧传递 i ig = 忍= ( o ) ( 6 ) ( c ) ( d ) 注意此时g 可以看作域疡上的4 维线性空间该空间的可逆线性变 换是群g 的自同构群，反之亦然因为s 生成g ，s 中一定含该线性空间 的一组基这样必有一个可逆线性变换，即g 的一个自同构，把s 中含 的一组基变为o ，6 ，c 和d 从而可设a ，6 ，c ，d s 进一步考虑g 的自同 构还可设s 包含曲，n 6 c 或曲c d ，既有s = 扣，6 ，c ，d ，曲) ， o ，6 ，c ，d ，0 6 c ) 或s = a ，6 ，c ，d ，0 6 c d ) 第二章交换群上五度弧传递c 聊e y 图 1 7 若s = t o ，6 ，c ，d ，口6 ) ，则x = c a y ( g ，s ) 中有一个3 一圈过弧( 1 ，) ， 但没有3 圈过弧( 1 ，c ) 这样x 不是弧传递的。若s = 。，6 ，c ，d ，0 6 c ) ，由 命题2 4 中的( 1 ) 知x 非正规，与假设矛盾这样可设s = 口，6 ，c ，d ，n 6 c d 设t = n ，6 ，c ，田，y = c a y ( g ，t ) 则y 是4 维立方体0 4 容易 验证y 中与1 距离为4 的点只有一个，即n k d 由x 的点传递性得 x 型国2 。由命题2 4 知x 正规，从而a u t ( x ) 兰乏a u t ( g ，s ) 明 显，a u 七( g ，s ) 在s 上传递且a u t ( g ，s ) 中固定曲c d 的子群在丁上4 一 传递这样，a u t ( g ，s ) 型昆，且a u t ( x ) 些墨s 5 因为& 作用在 s = 。，6 ，c ，d ，曲c d ) 上是2 - 传递的，故x 是2 一弧传递的注意到3 弧 一( 1 ，c ，c d ，d ) 在一个4 一圈上，而3 弧一( 1 ，n 6 ，6 c ) 不在任何4 圈上这 样x 不是3 一弧传递的，从而x 是2 一传递的此为定理中情形( 1 ) i i i g = 霹= ( 口) ( 砷( c ) ( d ) ( e ) 因为吲= 5 且( s ) = g ，存在g 的自同构把s 变到 o ，6 ，c ，d ，e ) 这 样可设s = n ，6 ，c ，d ，e ) 此时x = e a y ( g ，s ) 同构于5 维立方体q 5 所 以x 是2 - 传递的且a u t ( x ) = 罐，此为定理中情形( 2 ) 这样我们可设x = c a y ( g ，s ) 非正规下面考虑命题2 4 中列出的非 正规情形对应图的弧传递性及其中弧传递图的自同构群以及s 一传递性 首先，容易看出( 4 ) ，( 1 5 ) ，( 1 9 ) ，( 2 0 ) 都是弧传递的( 其中( 4 ) ，( 1 5 ) ， ( 1 9 ) ，( 2 0 ) 表示在命蹯24 中的序号，下同) 这些弧传递图的的自同构群 以及s 一传递性如表1 所示，它们恰好是定理中的情形( 3 ) ，( 4 ) ，( 5 ) ，( 6 ) 第二章交换群上五度弧传递嘞f e y 图 序号 x = c a y ( g ，s ) a u t ( x ) s ( 4 ) q 5 霹w 昆 2 ( 1 5 )训z xs 5 2 ( 1 9 )蚝5 ( s 5 s 5 ) 忍 3 ( 2 0 )诋6 6 嚣；& z 2 2 1 8 表l 对于命题2 4 中的情形( 1 2 ) ，g = z 。五邑= ( n ) ( 6 ) ( c ) ，m 3 ，s = n ，。一1 ，6 ，6 ，c ) ，x = c k q 3 当m = 4 时，x = q q 3 岩q 5 ， 这恰好是定理中的情形( 7 ) 当m 3 且4 时，x 是非弧传递的，其证 明将在下面给出对于命题2 4 中的情形( 1 6 ) ，g = 易。= ( n ) ，m 3 ，s = 口，口，o ”+ 1 ，口1 ，n m ) ，x = m _ 当m = 3 时，x = 岛 娲】竺凰， 这恰好是定理中的情形( 8 ) 当m 3 时，x 是非弧传递的，其证明将在下 面给出对于命题24 中的情形( 2 1 ) ，g = 磊。么= ( 口) ( 6 ) ，m 2 ，s = n ，口一，6 ，6 ，”6 2 ) ，x = 0 3 d c k 当m = 2 时，x = 日3 d g 型q 2 ， 这恰好是定理中的情形( 9 ) 当m 2 时，x 是非弧传递的，证明也将 在下面给出 下面证明命题2 4 中其它情形对应的图都是非弧传递的对情形( 2 ) 和( 8 ) ，因为以点1 为起点的弧中有些在3 - 圈中而有些不在，故x 不是弧 传递对情形( 1 ) ，则有g = 毋= ( n ) x ( 6 ) ( c ) ( d ) ，s = o ，b ，c ，d ，曲c ) 图2 画出了与x 中的点1 距离不超过2 的x 的一个子图 第二章交换群上五度弧传递g a e y 图 0 6 n c 6 c n d o k d 6 d c d 1 9 图2 通过图2 可以看出过x 中弧( 1 ，n ) 共有1 0 个4 _ 圈，而过弧( 1 ，d ) 只有4 个4 _ 圈则在a u t ( x ) 1 作用下不能把。传到d ，所以x 是非弧传 递的 余下的情形对应的图都是非弧传递的，其证明与情形( 1 ) 的证明类 似证明中需要用到以下事实，其中所用符号与命题2 4 中的符号一致 情形( 3 ) ，过弧( 1 ，o ) 有1 0 个4 一圈，而过弧( 1 ，c ) 有4 个4 一圈；情形 ( 5 ) ，过弧( 1 ，。) 有6 个缸圈，而过弧( 1 ，6 ) 有4 个4 一圈；情形( 6 ) ，当 m = 3 时，以1 为起点的弧有些在3 - 圈中而有些不在，当m 4 时， 过弧( 1 ，c ) 有4 个4 _ 圈，而过弧( 1 ，n ) 的4 - 圈多于4 个；情形( 7 ) ，当 m = 3 时，以l 为起点的弧有些在3 一圈中而有些不在，当m 4 时， 过弧( 1 ，6 ) 有4 个4 - 圈，而过弧( 1 ，口) 的4 - 圈多于4 个；情形( 9 ) ，过 弧( 1 ，o ) 有7 个4 _ 圈，而过弧( 1 ，6 ) 有4 个垂圈；情形( 1 0 ) ，当m = 3 时，过弧( 1 ，o ) 有1 个3 - 圈而过弧( 1 ，6 ) 有2 个3 _ 圈，当m 4 时， 以1 为起点的弧有些在3 一圈中而有些不在；情形( 1 1 ) ，当m = 3 时，以 1 为起点的弧有些在3 - 圈中而有些不在，当m 4 时，过弧( 1 ，6 ) 有6 第二章交换群上五度弧传递强y j e y 图 2 0 个4 _ 圈，而过弧( 1 ，口) 的4 一圈少于6 个；情形( 1 2 ) ，当m = 3 时，以1 为起点的弧有些在3 - 圈中而有些不在，当m 4 时，过弧( 1 ，6 ) 有4 个 4 圈，而过弧( 1 ，n ) 的4 - 圈少于4 个；情形( 1 3 ) ，过弧( 1 ，o ) 有4 个3 一 圈，而过弧( 1 ，6 ) 有2 个3 一圈；情形( 1 4 ) ，过弧( 1 ，0 2 ) 有4 个3 一圈，而 过弧( 1 ，6 ) 有2 个3 一圈；情形( 1 6 ) ，过弧( 1 ，口”) 有4 个3 - 圈，而过弧 ( 1 ，o ) 有2 个3 - 圈；情形( 1 7 ) ，过弧( 1 ，6 ) 有4 个3 一圈，而过弧( 1 ，n ) 有 2 个3 一圈；情形( 1 8 ) ，弧( 1 ，口”) 有4 个4 - 圈，而过弧( 1 ，n ) 的4 一圈多 于4 个；情形( 2 1 ) ，当m 2 时，过弧( 1 ，6 ) 有4 个3 圈，而过弧( 1 ，o ) 的4 一圈步于4 个；情形( 2 2 ) ，过弧( 1 ，。”) 有6 个4 - 圈，而过弧( 1 ，0 2 ) 的4 一圈少于6 个；情形( 2 3 ) ，过弧( 1 ，6 0 ”) 有6 个垂圈，而过弧( 1 ，) 的4 - 圈少于6 个 第三章交换群上二度有向弧传递c a y l e y 图 在本章中，我们将对交换群上二度有向c a y l e y 图进行弧传递分类 3 1 引言及预备知识 关于交换群上度数小于或等于3 的连通有向c a 讲e y 图的正规性有下 面的命题 命题3 1 1 设x = c a y ( g ，s ) 是有限交换群g 的度数小于或等于3 的 连通c a y l e y 有向图，则除下列情形外，x 都是正规的： ( 1 ) g = 历。= ( n ) ( n 2 ) ，s 型 o ，o ”1 ) ，x 型瓯【2 蜀】i ( 2 ) 。g = 磊易= ( o ) ) 伽 2 ) ，s 兰b 口“凡x 垡f 2 尬 ； ( 3 ) g = 磊= ( 。) ，s = g 1 ) ，x 型段i ( 4 ) g = 玩= ( n ) ，s = o ，0 3 ，n 5 ) ，x 型凰，3 i ( 5 ) g = 历玩= ( 口) ( 6 ) ，s 呈 n ，o 一1 ，b ，x 型q 3 7 ( 6 ) g = z 2 。 = ( n ) ( c ) ( n 2 ，m 1 ) ，s 全； n ，o “+ 1 ，c ) ，x 会! g 【2 k 1 c k i ( 7 ) g = z 。易z m = ( n ) ( u ) c ) ( 札 2 ，m 1 ) ，s 型 o ，口札，c ) ，x 型 g ( 2 甄】； ( 8 ) g = 2 2 。= 血) ( 仲 2 ) ，s 垒! ( 口，口”+ 1 ，n “) j ( 9 ) g = z 。为= ( 。) ( u ) ( 付 2 ) ，s 垒； d ，n “，“) i ( 1 0 ) ，g = 玩忍= ( n ) u ) ( 2 ) ，s 竺 o ，c ，口) i ( 1 1 ) g = 互。= ( 。) m = 4 女+ 1 ，女 o ) ，s 型 o ，舻“，o “+ 1 ) i 2 1 第三章交换群上二度有向弧传递唰e y 田 2 2 ( 1 2 ) g = z 如= ( o ) m = 4 七十1 ，七 o ) ，s g o ，0 2 ”+ 1 ，o “+ 1 ) i ( 1 3 ) g = z 札= ( 口) ( n = 4 七+ 1 ，七 o ) ，s 羔 n ，凸2 ”+ 1 ，0 3 “+ 1 ； 。 ( 1 4 ) g = z 4 。z 2 = ( z ) ( 可) ( 礼= 2 七+ 1 ，七 o ) ，s 宝! 。，。2 “+ 1 ，z “+ 1 可) i ( 1 5 ) g = z 。z 4 = ( 。) ( u ) ( 1 = 4 七，七 o ) ，s 垒! o ，口副2 ，。u ) i ( 1 6 ) g = 磊毛= ( 。) ( 掣) ，s 宝! 。”“可，。” g “，茁q m h 可一1 ) ，钍= ( m