（基础数学专业论文）完全三部图k222的弧传递zn正则覆盖.pdf

完全三部图垃：2 ，2 的弧传递磊一正则覆盖 摘要：设r 是有限无向简单正则图若i 、没有孤立点，我们称图r 是弧 传递的或对称的，如果r 的自同构群a u t ( f ) 传递地作用在r 的弧集合上本 文讨论了完全三部图施f 2 t z 的弧传递z - 正则覆盖，得到了几类新的4 度对称 图，其中佗= 4 k 或扎= 4 k 且k 三2 ( r o o d4 ) 特别地，我们得到了一类新的点稳 定子无界并且不是两图的字典式积的4 度对称图 关键词：图鲍，2 ，2 对称图，正则覆盖，循环覆盖，电压，提升 o na r c t r a n s i t i v e o ik 2 ，2 ，2 a b s t r a c t ：l e trb eaf i n i t eu n d i r e c t e ds i m p l er e g u l a rg r a p hw h i c hh 第n oi s o l a t e d v e r t i c e s w es a yt h a t1 1i sa r c t r a n s i t i v eo rs y m m e t r i cg r a p h ，i fi t sf u l la u t o m o r p h i s mg r o u p a u t ( f ) a c t st r a n s i t i v e l yo ni t sa r cs e t i nt h i sp a p e r ，w ei n v e s t i g a t et h ea x e t r a n s i t i v ez - r e g u l a rc o v e r i n g so fk 2 ，2 ，2 ，a n do b t a i ns e v e r a ln e wi n f i n i t ef a m i l i e so f4 一v a l e n ts y m m e t r i c g r a p h sa st h ec o v e r i n gg r a p h so f r 2 ，2 ，2b y 磊，w h e r en = 4 ko rn = 4 ka n dk 兰2 ( m o d 4 ) i np a r t i c u l a x ，w eo b t a i na ni n f i n i t ef a m i l yo f4 - v a l e n ts y m m e t r i cg r a p h s ，w h i c ha r en o t al e x i c o g r a p h i cp r o d u c to ft w og r a p h sa n dh a su n b o u n d a r yo r d e ro t t h ev e r t e x - s t a b i l i z e r k e yw o r d s ：鲍，2 ，2 ，s y u m a e t r i cg r a p h ，r e g u l a rc o v e r i n g ，c y c l ec o v e r i n g ，v o l t a g e ， l i f t i n g 2 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明本声明的法律责任由本人承担 学位论文作者： i 采呻 j 日期：力卵年歹月 e t 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大 学。根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有 关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权 郑州大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用 影印、缩印或者其他复制手段保存论文和汇编本学位论文本人离校后发表、 使用学位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍 然为郑州大学。保密论文在解密后应遵守此规定 学位论文作者： 王8 卞 日期：川年f 月 日 1引言 在本篇文章中，若没有特别声明，所指的图均为有限、无向、简单的连通 图，对于群论中的概念和记号，这里不再定义，请参考文献1 1 ，2 ，3 】 给定一个图r ，我们用v ( r ) 、e ( r ) 、a r c ( f ) 和a ：= a u t ( p ) 分别表示图r 的顶点集、边集、弧集和全自同构群对于两个顶点u 和v ，我们用让一秒来表 示它们相邻，用 u ，秽) 或u u 来表示连接u 和v 的边，用( u ，口) 表示从u 到口的 弧 设g a u t ( r ) ，我们说图r 分别是g 点传递，g - 边传递的，和g 弧传递 的，若a u t ( r ) 的子群g 传递地作用在点集v ( r ) ，边集e ( r ) 上，和弧集a r c ( r ) 上特别的，当g = a u t ( r ) 时，a 点传递，a 边传递的，和a 弧传递的，分 别称图r 是点传递，边传递，和弧传递的其中弧传递图又称对称图 争弧 是( 3 + 1 ) 重有序点对( v o ，v l 刀。) ，其中耽一1 与v i 相邻，并且对1si s ，有 一，v i ，换句话说，争弧就是一条长为s 的有向路一个图r 说是s - 弧传递 的，若a u t ( x ) 在它的舅弧集合上传递特别地，m 弧传递即为顶点传递，1 弧传递即为弧传递或对称的弧传递图r 说是争正则的，如果对任意两个争 弧都存在唯一的自同构，把其中一条弧映为另一条因此，如果一个图是5 一正 则的，则它的自同构群传递地作用在s 一弧集合上，且争弧的稳定子群是1 集 合q 上的一个置换群g 说是半正则的，若对于任意q q ，有稳定子群g 。= 1 ； 说是正则的，若它是半正则且传递的 一个图f 关于投射p ：于一r 说是图r 的覆盖图，若p 是从y ( 于) 到v ( r ) 的满射且对任意的顶点钉v ( r ) 和西p - i ( 口) ，满足p l 肺) ：i ( 9 ) + n ( v ) 是双 射图f 称为是r 的覆盖图，图r 称为是于的基图，每个p 一，( 钉) 称为f 的一个 纤维r 的关于投射p 的覆盖图说是正则覆盖( 肝覆盖) ，若存在a u t ( f ) 的子 群k ，使得k 在y ( 亍) 和e ( 于) 上均半正则作用，且满足映射h ：f - - - - - 4 于k 是同 构，商映射f f k 是p 和h 的合成p ( 为方便起见，本文中的映射作用按从 左到右次序) 若f 是连通的，则k 称是覆盖变换群若a a u t ( r ) ，ae a u t ( f ) ， 满足却= p a ，则我们称a 是q 的一个提升，q 是a 的投射 关于半对称图的研究是由f o l k m a n 4 】引入的，当时称之为线对称他构造 了一些半对称图的无限类，证明了2 p ，劬2 个点的半对称图不存在，并提出了一 系列问题，激起了学术界的研究兴趣d u 和x u 5 】对2 p q 阶的半对称图进行 了分类l u 等 6 】对印2 阶的3 度半对称图进行了完全分类研究m a l i n c 等 【7 】对印3 阶的3 度半对称图进行了分类研究，另外，印阶和8 p 2 阶及1 2 p 阶， 印z 口【8 】的3 度半对称图的研究也已经完成最近，f e n g 对印3 阶的3 度半对称 图进行了完全分类研究 关于对称图的研究主要包括两个方面：一方面是关于对称图的分类；另一 方面是构造新的对称图，发现新的图例 自上世纪七十年代，关于对称图分类的研究引起了国内外许多学者的兴 趣，并取得了重大进展主要是对不同阶数的对称图来进行分类1 9 7 1 年， c h a o 9 】已经完成了对素数个顶点的对称图的分类之后，随着有限单群分类工 作的重大突破，到1 9 8 7 年，c h e n g 和o x l e y 1 0 】确定了所有的印为素数) 阶弱 对称图1 9 9 1 年，w a n g 和x u 1 l 】对却( p 为素数) 阶对称图进行了分类 1 9 9 3 年，p r a e g e r ，w a n g 和x u 1 2 完成了册，q 为素数) 阶对称图的完全分类 自g r o s s 和t u c k e r 1 3 】引入了用组合的手段通过电压来对覆盖图进行刻画的 方法以后，有关图的正则覆盖理论已被广泛应用于图的对称性研究，已经成为 构造新的对称图的有效方法因此，这种方法的引入在代数图论中具有非常重 要的作用和意义具有代表性的结果有：2 0 0 2 年，f e n g 和k w a k 1 4 】通过立方 体q 。的1 正则循环覆盖，构造了一类3 度对称图之后，他们又得到了完全 二部图飓，3 的s 正则覆盖的分类【1 5 ，这里1 s 5 同年，f e n g 和w a n g 1 6 】 对立方体q s 的正则循环覆盖进行了分类，并得到了一类3 度1 正则图第二 年，f e n g 和w a n g 2 4 】完成了立方体q 3 的s - 正则循环覆盖的完全分类最近， w a n g 和h a o 对h e a w o o d 图的边传递磊一正则覆盖进行了分类，得到了一类2 正则图和一类1 正则图 2 本篇文章主要研究了完全三部图，。，。的弧传递循环正则覆盖图，通过对 礼取值的不同情况进行讨论，得到了几类新的4 度对称图，其中一类具有无界 的点稳定子群，但不是字典式积 本篇文章的主要结果如下： 定理1设m = 磊，亍= 鲍2 2 妒m 是，2 ，2 的连通的弧传递 扛正则覆 盖，并且m 是保纤的，则于的电压配置妒如下： ( 1 ) l ：口= 0 ，b = 0 ，c = 1 ，d = 一1 ，e = 0 ，= 1 ，g = 一1 ( 2 ) 九：a = 0 ，b = 2 k ，c = 1 ，d = 2 k 一1 ，e = 2 k ，f = 1 ，g = 2 k 一1 其中 礼= 4 k ( 3 ) 西3 ：8 = 2 k ，b = k ，c = l ，d = 七一l ，e = k ，= l ，9 = k 1 其中 n = 4 k ，k 兰2 ( r o o d4 ) ( 4 ) 九：a = 2 k ，b = 一k ，c = 1 ，d = 一k 一1 ，e = 一k ，f = 1 ，g = - k 一1 其中 礼= 4 k ，k 兰2 ( r o o d4 ) 进一步，覆盖图尬，2 ，2x 妒。儿鲍，2 ，2 咖m ，k 2 ，2 ，2 如m 和鲍，2 ，2 籼m 都是对 称图并且k 2 ，2 ，2 咖。m 掣q 【2 所】；，z ，z 如i ，的自同构群的点稳定子是无界的 且阶数大于等于2 2 七；鲍 2 ，2 加m 和鲍，2 ，：咖m 的自同构群的点稳定子都同构 于d 8 3 2 预备知识 导出覆盖和提升问题 g r o s s 和t u c k e r 1 3 引入了用组合的手段通过电压来对覆盖图进行刻画的方 法设r 是一个图，是一个有限群，设a a r c ( r ) ，我们用a - 1 表示弧a 的 逆r 的电压配置( 或k 电压配置) 是一个函数 ：a r c ( r ) 一k ， 它满足：对任意的弧a a r c ( r ) ，都有( n _ 1 ) = ( n ) ，咖的值称为电压，k 为 电压群由电压配置砂：a r c ( r ) _ k 导出的图r 西k 的顶点集为v ( r ) 丈k ，边 集为e ( f ) k ，从而rx 毋k 的连结顶点( u ，9 ) 和( v ，( o ) 夕) 的边为( e ，夕) ，其中a = ( u ， ) a ( r ) ，9 k ，e = 仳可显然，导出图rx 毋k 是关于自然投射p ：r 币k r 的图r 的一个覆盖对任意g k ，( 牡，9 1 ) v ( rx 西) ，定义 ( t 工，9 ) g ：= ( “，9 9 ) ， k 等同于a u t ( rx 毋k ) 的一个子群半正则地作用在v ( r 咖k ) 上从而，r 毋k 可以看作是一个k 一覆盖给定图r 的一个支撑树t ，一个电压配置说是口 约化的，若支撑树弧t 上的电压都是平凡的g r o s s 和t u c k e r 证明了图r 的 任一个正则覆盖图于都是由d 约化电压配置妒生成的，t 是r 的任意给定的 支撑树从而我们可以得到，若咖是约化的，覆盖图f 是连通的当且仅当余树 弧上的电压生成电压群 命题2 1【1 3 1 任意图g 的一个连通的群覆盖都可以由一个约化的肝电 压分配导出，这时，图g 任意取定的支撑树上的电压为平凡电压 设于是关于投射p 的r 的肝覆盖若乜e a u t ( r ) ，ae a u t ( f ) ，满足a p = p a ， 则我们称a 是q 的一个提升，o t 是5 的投射a u t ( r ) 的子群的一个提升与 h u t ( f ) 的一个子群的投射的概念是互为解释的当然，这些子群的提升和投射 分别是a u t ( f ) 和a u t ( r ) 的子群特别地，若覆盖图是连通的，那么覆盖变换 群k 是单位群的提升也就是说，k = ae a u t ( i ) ：p = 卸 显然，若a 是q 的一个提升，则k a 是q 的所有提升 4 下面的命题是( 1 7 】中定理4 2 的特殊情况 命题2 2设a u t ( fx 砂k ) 叶r 是一个连通的k 一覆盖，那么r 的一个自同 构口提升当且仅当a 可以扩充为k 的一个自同构 r 的一个自同构是否能够提升可以根据电压如下来判断考虑弧上的电压 配置以自然方式扩充到途上的电压配置给定o le a u t ( r ) ，我们定义一个从以给 定顶点为基础的基本闭途的电压集合到电压群k 的映射 a ：( ( g ) ) 丘= ( c n ) ， 其中c 取遍所有经过的基本闭途，砂( c ) 和( 俨) 分别是c 和c q 的电压注 意，若k 是交换的，a 不依赖于基点的选择，经过v 的基本闭途可以由r 的 余树弧对应的基本圈代替 下个命题是 1 8 】中的定理1 1 中的结论 命题2 3设丁是图r 的一个支撑树，电压配置，砂都是正约化的，那 么连通正则覆盖图f 西k 和r 咖k 等价当且仅当对r 的任意的余树弧( u v ) ， 存在仃a u t ( k ) 使得( u u ) 矿= 妒( 删) 有关图f 的自同构的提升的更多结果，请读者参考文献【2 0 ，2 1 ，2 2 ，2 3 】 5 3 定理1 的证明 设v ( k 2 ，2 ，2 ) = 0 ，1 ，2 ，3 ，4 ，5 ，不失一般性，我们选取 0 ，1 ) ， 2 ，3 】， 4 ，5 作为 完全三部图鲍 2 。的块，如图1 ( n ) 所示我们考虑鲍 2 ，2 的极小弧传递子群r ， 这时，r 必包含鲍 2 。的极小点传递子群日，且r 包含尬2 ，z 的点稳定子群d s 在邻域上正则作用的子群k 其中h 竺磊或昆，k 竺z 4 或霹 注意到，a u t ( k 2 2 2 ) 竺z 2w r 昆笺z 2 s 4 我们设 o = ( 0 2 4 1 3 5 ) ，尻= ( 0 2 5 ) ( 1 3 4 ) ，侥= ( 0 3 ) ( 1 2 ) ( 4 5 ) ，盯= ( 2 5 3 4 ) ， n = 盯2 = ( 2 3 ) ( 4 5 ) ，死= ( 2 4 ) ( 3 5 ) ，7 = ( 0 1 ) ( 2 3 ) ( 4 5 ) 则上述置换都是鲍2 1 z 的自同构令h = ( o ) 或( 既岛) ，k = ( 口) 或机) 忆) ， 则日为鲍2 ：的极小点传递子群，k ( a u t ( k 2 2 ，。) ) o 在邻域上正则作用于是 我们有： 引理3 1设亍为f = k 2 ，2 。的连通的弧传递磊正则覆盖，则有下列之 一成立： ( 1 ) q ，盯提升； ( 2 ) q ，丁l ，丁2 提升； ( 3 ) 尻，仍，盯提升； ( 4 ) 屁，忍，n ，死提升 特别地，总有7 1 提升 取定鲍2 z 的支撑树r ，其边集为： 【o ，2 ，| 【o ，3 ， o ，4 ，( o ，5 ， 1 ，4 如图l ( b ) 所示 6 5 o1 25 o 4343 ( a )( b ) 2 图1 ( a ) 图k 2 ，2 ，2 ，( b ) 虬，2 ，2 的支撑树r 设砂是耽幺：的一个电压分配，电压分配砂按照如下方式给出：支撑树丁 的弧上的电压为零，余树弧上的电压分别设为a ，b ，c ，d e ，g 其中 a = 矽( 5 ，1 ) ，b = ( 1 ，3 ) ，c = ( 3 ，5 ) ，d = ( 5 ，2 ) ，e = 咖( 2 ，1 ) ，= 咖( 2 ，4 ) ，g = 西( 4 ，3 ) 在完全三部图鲍，2 ：中任意取定一个基点，不妨取基点0 ，则过基点0 的基本圈 c 有如下七个： 0 5 1 4 0 ，0 4 1 3 0 ，0 3 5 0 ，0 5 2 0 ，0 2 1 4 0 ：0 2 4 0 ，0 4 3 0 这七个基本圈分别由余树弧( 5 ，1 ) ，( 1 ，3 ) ，( 3 ，5 ) ，( 5 ，2 ) ，( 2 ，1 ) ，( 2 ，4 ) ，( 4 ，3 ) 生成我 们给出所有鲍 2 ，：的基本圈c 的电压值和在q ，伪，伤，仃，n ，7 2 ，丁作用下的像圈 的电压值表 如图表2 所示 7 c 砂( c ) q + 成憨 0 5 1 4 0a- b e- b e g 一 一d c 0 4 1 3 0 bb + c + d + e e 七b g 一| c + d 0 3 5 0cd g 0 5 2 0d d b g 0 2 1 4 0 e 七g b e - b c d e - b c d e 0 2 4 0 1 一e - d + a e一口一b c 0 4 3 0 g e a + d e l c c ( c ) 盯+ 百呓 f 0 5 1 4 0n- b e一a一6 一en 0 4 1 3 0b e n ee ne 一口 0 3 5 0c 9 c | 一e 0 5 2 0dc g一99 b 0 2 1 4 0e n e - b a 一ea + b 0 2 4 0 dc 一1 n + b + c 0 4 3 0 9 d 一d- - a + d + e 表2 引理3 2 设 ，= 磊，亍= k 2 ，2 ，2 毋i 彳是鲍，2 ，2 的连通的弧传递的m 一正 则覆盖，使得丁1 提升，那么于的电压配置有以下几种情形； ( 1 ) 1 ：a = 0 ，b = 0 ，c = 1 ，d = - 1 ，e = 0 ，= 1 ，g = - 1 ( 2 ) 锄：a = 0 ，b = 2 k ，c = 1 ，d = 2 k 一1 ，e = 2 七，= 1 ，g = 2 尼一1 其中 亿= 4 k ( 3 ) 九：a = 2 k ，b = k ，c = 1 ，d = k 一1 ，e = k ，= 1 ，9 = k 一1 其中 n = 4 k ，k 兰2 ( r o o d4 ) ( 4 ) 机：a = 2 k ，b = 一七，c = 1 ，d = 一k 一1 ，e = 一k ，= 1 ，g = 一七一1 其中 8 n = 4 k ，k 三2 ( m o d4 ) 进而，如果是上述情形之一，则k 提升，且覆盖图( 2 2 2 毋。m ，k 2 ，2 ，2x 4 , ：m ， ，2 ，2 如m 和鲍2 ，2 曲。m 都是对称图 证明：首先，我们设q ，n 提升，则由命题2 2 知，q ，贯可以扩充成为磊 的自同构由表2 知，q 4 ( c ) = - d ，a + ( d ) = - y ，r ；( c t ) = 9 ，从而有c ，d ，9 的阶数都 相等因此，( c ) = ( d ) = ( ，) = ( 9 ) 因为( 厂) = ( ，一e ) ，所以e ( ，) 又因为( e ) = ( ，+ 9 一b e ) ，所以b ( n 因为( b ) = ( 口一e ) ，所以n ( n 由 2 1 2 2 的磊覆盖图 是连通的，所以( 口，b ，c ，d ，e ，9 ) = 磊从而，我们得到c ，d ，9 绞 注意，群磊的任意自同构都有形式z 一妇，其中k 彩，z 磊 我们不妨假定c = 1 ，则由表2 知n + ：z 一一如，一d 东，z 磊从而有 n = d 3 + d 2 + d + d 9 ，b = 9 + d 4 ，c = 1 ，d = d ，e = d 2 + d 3 ，= d 2 ，9 = 9 因为叶：z 一，z ，磊，z 磊，所以有9 = ，d 且，2 = 1 ，则d 4 = 1 ，9 = d 3 ，从而 得到： n = d 3 + c f 2 + d + 1 ，b = d 3 + 1 ，c = 1 ，d = d ，e = d 3 + d 2 ，= d 2 ，9 = d 3 又因为q ( b ) = n e ，有f b = 凸一e ，即d 2 ( d + 1 ) = d 3 + 1 ，有d 2 = 1 ，则= 2 ( d + 1 ) ，b = d + 1 ，c = 1 ，d = d ：e = d + 1 ，= 1 ，9 = d 又因为百( o ) = 一n ，层p n = y a ，故 2 a = 4 ( a + 1 ) = 0 从而我们得到电压配置 ：1 7 , = 2 ( d + 1 ) ，b = d + 1 ，c = 1 ，d = d ，e = d + 1 ，= 1 ，9 = d 并且d 2 = 1 ，4 ( d + 1 ) = 0 在这样的电压配置下，我们验证a ，n ，仉您，丁是否提升结合图表2 ，我们计 算各电压在矿下的像， q + ( n ) = - d a = - 2 a ( a + 1 ) = - 2 ( d + 1 ) = - b e ， a + ( 6 ) = - d b = 一d ( d + 1 ) = - ( a + 1 ) = 3 ( a + 1 ) = b + c + d + e ， 9 a + ( c ) = - d c = 一d ， o l + ( d ) = _ d 2 = - 1 = - f ， o z + ( e ) = - d e = 一d ( d + 1 ) = 一( d + 1 ) = 1 + d 一2 ( d + 1 ) = ，+ 9 一b e ， o t + ( 厂) = 一彤= - d = 1 一( 1 + d ) = ，一e ， o t + ( 9 ) = 一d 9 = _ d 2 = 一1 = d + 1 2 ( d + 1 ) + d = e o + d 因此，q ：z 一一如，一d 露是磊的一个自同构所以由命题2 2 知，q 提升 类似地，我们有 贯( n ) = ，n = n = 2 ( d + 1 ) = 一2 ( d + 1 ) = 一o ， 霄( 6 ) = ，6 = b = d + 1 = o e ， 百( c ) = ， 贯( d ) = 问= d = 9 ， 叶( e ) = ，e = e = d + 1 = - 3 ( d + 1 ) = - b 一口， 百( ，) = ，2 = 1 = c ， 贯( 9 ) = 向= 9 = d 因此，贯：z 一，z ，= 1 露是磊的一个自同构所以由命题2 2 知，n 提 升 盯+ ( o ) = 盯+ ( 2 ( d + 1 ) ) = 2 9 ( e l + 1 ) = 2 ( d + 1 ) = - 2 ( d + 1 ) = 一b e ， 盯+ ( 6 ) = 仃( d + 1 ) = 9 ( d + 1 ) = ( d + 1 ) = e ， 盯( c ) = 9 ，矿( d ) = 9 d = d 2 = 1 = c ， 盯4 ( e ) = 盯( d + 1 ) = 9 ( d + 1 ) = d + 1 = n e ， 矿( ，) = 9 = d , c r ( 9 ) = 9 2 = 俨= 1 = 厂 因此，矿：z _ 9 ：r ，9 露是磊的一个自同构所以由命题2 2 知，盯提升 呓( o ) = 一n = - 2 ( c + 1 ) = - b e ， 霄( 6 ) = - b = 一( d + 1 ) = e 一口， 贯( c ) = 一c ， 霄( d ) = - d = 一9 ， 露( e ) = 一e ， 霄( ，) = - 1 ， 呓( 9 ) = - g = - d ， 因此，呓：z _ 一z ，一1 = 一c 玩是磊的一个自同构所以由命题2 2 知，7 2 提升 7 - + ( n ) = ( 一e ) 口= - d a = - 2 d ( d + 1 ) = 2 ( d + 1 ) = a ， 7 - ( 6 ) = ( ，一e ) 6 = - d b = - d ( d + 1 ) = - ( d + 1 ) = e a ， 7 i + ( c ) = ( ，一e ) c = - d c = - d = 一e + ， r ( d ) = ( ，一e ) d = _ d 2 = - 1 = 夕一b ， 7 - ( e ) = ( ，一e ) e = - d e = - d ( d + 1 ) = - ( d + 1 ) = 3 ( d + 1 ) = a + b ， 7 - + ( ，) = ( ，一e ) ，= - d = - ( d + 1 ) + 1 = 3 ( d + 1 ) + 1 = a + b + c ， 7 + ( 9 ) = ( ，一e ) 9 = 一d g = _ d 2 = - 1 = - 2 ( d + 1 ) + d + 1 + d = 一a + e + d 因此，丁：z _ 一d x ，一d 玩是磊的一个自同构所以由命题2 2 知，下也提 升 综上所述，当电压配置矽为： a = 2 ( d + 1 ) ，b = d + 1 ，c = 1 ，d = d ，e = d + 1 ，= 1 ，g = d 并且a n = 1 ，4 ( d + 1 ) = 0 时，a ，仃，丁1 ，仡，7 均提升，故k ，疗提升，从而在这样的 电压配置下所得的图均为对称图 下面我们在电压下，对群磊中n 的取值进行分情况讨论： 当n 为奇数时，由4 ( d + 1 ) = 0 ，我们得到d = 一l ，即得到电压配置： ( 1 ) 咖1 ：a = 0 ，b = 0 ，c = 1 ，d = 一1 ，e = 0 ，= 1 ，g = 一1 从而我们得到覆盖图鲍，2 ，2 如磊 如下图3 所示 图3 覆盖图k 2 ，2 ，2 毋1 磊 4 n 一1 0 n 一1 2 n 一1 当n 为偶数时，如果d = 一1 ，那么与情形( 1 ) 相同，得到相同的覆盖图 k 2 2 1 2 2 咖。磊现在我们假定d - 1 设n = 2 m ，由4 ( d + 1 ) = 0 可得，d = m 一1 又由于d 2 = 1 当且仅当m 2 2 m 兰o ( m o d2 m ) ，即m 兰o ( m o d2 ) ，从而仇为偶数 1 2 设m = 2 k ，即n = 4 k ，则由4 ( d + 1 ) = 0 可得， d = 2 k 一1 ，d = k 一1 ，d = 一七一1 当d = 2 k 一1 时，由于d 2 = 1 当且仅当4 k ( k 一1 ) 三o ( m o d4 k ) ，后者恒成立 从而我们得到电压配置： ( 2 ) 如：a = 0 ，b = 2 k ，c = 1 ，d = 2 k 一1 ，e = 2 k ，= 1 ，g = 2 k 一1 其中凡= 4 k 从而我们得到覆盖图，2 2 晚磊如图4 所示 0 0 图4 覆盖图 2 ，2 ，2 晚磊 一1 - 1 当d = k 一1 时，由于d 2 = 1 当且仅当k ( k 一2 ) 三0 ( m o d4 k ) ，即七三2 ( r o o d4 ) 从而我们得到电压配置： ( 3 ) 3 ：a = 2 k ，b = 良，c = 1 ，d = 七一1 ，e = 七，= 1 ，g = 七一1 其中n = 4 k ，七三 2 ( r o o d4 1 从而我们得到覆盖图恐，2 ，z 如磊如图5 所示 图5 覆盖图k 2 ，2 ，2 毋3 磊 当d = 一k l 时，由于d 2 = 1 当且仅当k ( k + 2 ) 三0 ( m o d4 k ) ，即k 三2 ( m o d4 ) 从而我们得到电压配置： ( 4 ) 九：a = 2 k ，b = 一k ，c = 1 ，d = 一k 一1 ，e = - k ，= 1 ，g = - k 一1 其中n = 4 k ，k 三2 ( r o o d4 ) 从而我们得到覆盖图k 2 ，z ，2 如磊如图6 所示 图6 覆盖图鲍，2 ，2x # 4 磊 其次，我们设防，仍，7 1 提升，那么所，成，百可以扩充成为磊的自同构 由表2 知，贯( d ) = g ，廛( g ) = c ，钟( c ) = ，从而有c ，d ，f ，9 的阶数都相等因此， ( c ) = ( d ) = ( f ) = ( 9 ) 因为( 9 ) = ( e 一，) ，所以e ( 9 ) 因为( e ) = ( 一d c b e ) ，所 以b ( 夕) 又因为( b ) = ( 口一e ) ，所以n ( 夕) 由 2 2 的磊覆盖图是连通的，所 以( a ，b ，c d ，e 夕) = 磊从而，我们得到c ，d ，夕z 注意，群磊的任意自同构都有形式z 一妇，其中七召，z 磊 我们不妨假定c = 1 ，结合表2 知，成：z _ 知，废：z 一9 x ，贯：z _ 如，显然 有，d = d ，d = 夕，f 2 = 1 ，夕2 = 1 ，则9 = d ，= 1 又由向= e 一，知，e = d + 1 由 厂2 = - d + n e 知，o = 2 ( d + 1 ) 由f e = - b o j 知，b = 一3 ( d + 1 ) 由f a = 一。 知，2 a = 4 ( e l + 1 ) = 0 从而我们得到电压配置 ：o = 2 ( d + 1 ) ，b = d + 1 ，c = 1 ，d = d ，e = d + 1 ，= 1 ，9 = d 并且d 2 = 1 ，4 ( d + 1 ) = 0 在这样的电压下，前面我们已经验证了矾7 1 ，见，丁都是提升的下面我们只 验证风，侥是否是提升的 p ；( 口) = ，o = 2 ( d + 1 ) = - 2 ( d + 1 ) = - b e ， 所( 6 ) = ，6 = d + 1 = 2 ( d + 1 ) 一1 一d = e + b 一夕一， 所( c ) = f c = ， 所( d ) = f c t = d ， 所( e ) = r e = d + 1 = - 3 ( d + 1 ) = - 1 一d 一2 ( d 十1 ) = 一d c b e ， p ；( ，) = ，2 = 1 = - d + 2 ( d + 1 ) 一( d + 1 ) = - d + 口一e ， 所( 9 ) = f 9 = d = d + 1 1 = e 一， 因此，所：z 一知，= 1 磊是磊的一个自同构所以由命题2 2 知，岛提 升 废( o ) = g c z = 2 d ( d + 1 ) = - 2 ( , + 1 ) = - d 一1 一d 一1 = 一9 一f d c ， 廛( 6 ) = g b = d ( d + 1 ) = d + 1 = c + d ， 废( c ) = 9 c = 9 ， 店( c z ) = g d = d 2 = 1 = d + 1 一d = b 一夕， 16 佛( e ) ；9 e = d ( d - - f 1 ) = d + 1 = 一3 ( d + 1 ) = 一( d + 1 ) ( d + 1 ) - d - 1 = - b - e d c ， 店( ，) = g f = d = - 3 ( d + 1 ) 一l = - ( d + 1 ) 一2 ( d + 1 ) 一1 = - b a c ， 优 ) = 9 2 = d 2 = 1 = c 因此，店：z g x ，g 玩是磊的一个自同构所以由命题2 2 知，仍提升 综上所述，当电压配置为 a = 2 ( d + 1 ) ，b = d + 1 ，c = 1 ，d = d ，e = d + 1 ，= 1 ，g = d 并且d 2 = 1 ，4 ( d + 1 ) = 0 时，角，仍，o r ，n ，见，7 均提升从而k ，日提升，故我们可 以得到与前述几种情形相同的对称图 。 从而引理3 2 得到证明 引理3 3 设覆盖图于币。= k 2 2 2 母。磊，屯= ，2 ，2 屯磊，屯= k 2 2 2 如磊， 亍咖。= 鲍，2 ，2 九磊，则有 ( 1 ) r 妒。鲁瓯 2 髓】； ( 2 ) a u t ( t 锄) 的点稳定子群是无界的，其阶数大于等于2 2 匕 ( 3 ) a u t ( f 加) 的点稳定子群竺d 8 ； ( 4 ) a u t ( f 籼) 的点稳定子群兰d 8 证明：( 1 ) 通过图3 容易看出，覆盖图于锄竺g 2 k 1 】 ( 2 ) 通过图4 容易知道，置换咖= ( 2 0 ，3 0 ) ( 3 2 k ，2 2 七) ( 4 l ，5 1 ) ( 5 2 ，4 2 七+ 1 ) 是覆盖图 f 咖：的个自同构，故磊在自同构群a u t ( f 忱) 中非正规事实上，若z 璺a u t ( f 锄) ， 则a u t ( f 屯) 为投射，这表明于西：的任意自同构都是保纤维的从而覆盖图自同 构群的点稳定子群a 0 0 在屯。( 0 0 ) 上的作用是忠实的，显然这是矛盾的 可以验证置换伽= ( 2 0 ，3 0 ) ( 3 2 七，2 2 七) ( 4 1 ，5 1 ) ( 5 2 七十1 ，4 2 m ) ，妒1 = ( 2 1 ，3 1 ) ( 3 2 m ，2 2 m ) ( 4 2 ，5 2 ) ( 5 2 知+ 2 ，4 2 七十2 ) ，妒2 七一1 = ( 2 2 七_ l ，3 2 七一1 ) ( 3 铀- l 2 驰一1 ) ( 4 2 七，5 2 七) ( 5 0 ，4 0 ) 都是覆盖图 r 毋。的自同构，慨a 0 0 ，i o ，1 ，2 k 一1 ) 且( 伽，妒”一，妒2 七一1 ) 笺砺七，因而， i a o o i i ( 咖，妒1 j 一，妒z 南一) i22 驰随着七的变大，点稳定子群a 0 0 的阶数是无界 1 7 的另一方面，通过图4 可以看出，亍西：的任意两个不同顶点的邻域都不同， 因而于毋：不是两个图的字典式积 ( 3 ) 我们给出f 西。的树图的子图 如图7 所示 图7 覆盖图亍咖。的树图的子图 1 8 首先，证明屯的自同构群点稳定子a 0 0 在其点0 0 的邻域t = ( 2 0 ，3 0 ，4 0 ，5 0 ) 上的作用是忠实的即对任意u a o o ，且u - i t = 1 t ，则有u 。= 1 事实上，对任意u 1 a 0 0 ，且u 1 i t = 1 t ，则有u 1 分别固定点2 0 ，3 0 ，4 0 和5 0 ，及 它们的邻域 4 1 ，5 3 k + 1 ，l 七) ， 5 l ，4 3 七+ 1 ，l 3 k ， 3 1 ，2 k 一1 ，1 2 k ，( 2 1 ，3 k 一1 ，l o 如图7 所示，因为u 1 固定2 0 ，3 0 ，并且既过点2 0 又过点3 0 只有两个6 圈，即 ( o o ，3 0 ，5 l ，0 1 ，4 1 ，2 0 ，o o ) ，( 0 0 ，3 0 ，4 3 七+ 1 ，0 3 k + l ，5 3 k + 1 ，2 0 ，0 0 ) ，贝4u 1 要么固定点4 1 ，5 3 七+ 1 ，5 l 和4 3 m ，要么互换点4 l 和5 3 ，5 l 和4 3 南+ 1 从而u 1 固定点1 七和1 3 j b 同理，我们 也可以证明u 1 也固定点l o 和1 2 七，3 七一1 和5 3 七+ 1 ，5 l 和2 “2 k l 和4 3 七+ 1 ，4 1 和3 - 1 故a l l = 1 其次，证明点稳定子群a 0 0 笺d 8 因为a 0 0 在t 上忠实作用，则在同构意 义下，a 0 0 & 又因为a 0 0 包含d 8 ，故a 0 0 型& 或d 8 若a 0 0 竺s 4 ，则a 0 0 在氏1 ( o o ) 上是4 - 传递的，即存在u 2 a o d ，使得0 d 2 固 定点2 0 和5 0 ，互换3 0 和4 0 如图7 所示，由0 3 2 固定点2 0 和5 0 ，而过此两点只有 两个6 - 圈，即( 0 0 ，2 0 ，5 3 k + 1 3 3 七，1 2 七，5 0 ，o o ) ，( 0 0 ，2 0 ，1 ，4 ，2 七一1 5 0 ，o o ) ，则a 2 固定点4 l 和3 1 从而固定点1 l 和l s k - 1 因此u 2 要么固定0 。和3 七，要么对换0 ，和3 缸若 0 1 2 固定点0 。和3 七，因为于如是点传递的，则u 。固定图中所有点这与假设矛 盾若0 3 2 对换0 - 和3 七，则0 9 2 对换集合( 2 - ，3 - ) 和 5 m ，o k ，这是不可能的事 实上， o 七，0 2 七，0 3 k 为如不变的 故a o o 竺d s ( 4 ) 证明与情形( 3 ) 类似，给出覆盖图亍机的树图的子图 如图8 所示 1 9 图8 覆盖图于机的树图的子图 首先，证明f 币。自同构群点稳定子群4 0 0 在其点0 。的邻域t = 2 0 , 3 0 ，4 0 ，5 0 ) 上的作用是忠实的即对任意u 2 a 0 0 ，且u 2 i t = 1 t ，则有0 3 2 = 1 事实上，对任意0 j 2 a o o ，且峨i r = 1 t ，则有w 2 分别固定点2 0 ，3 0 ，4 0 和5 0 ，及 它们的邻域 4 1 ，5 k + 1 ，1 3 k ， 5 1 ，4 k + l ，l 七) ， 3 1 ，2 3 k 一1 ，1 2 k ， 2 1 ，3 3 k 一1 ，l o 如图7 所示，因为忱固定2 0 ，3 0 ，并且既过点2 0 又过点3 0 只有两个6 - 圈， 即( 0 0 ，3 0 ，5 1 ，0 l ，4 l ，2 0 ，0 0 ) ，( 0 0 ，3 0 ，4 k + h o k + 1 ，5 k + 1 j 2 0 ，0 0 ) ，则忱要么固定点4 1 ，5 七+ 1 ，5 1 和4 m ，要么互换点4 l 和5 ，5 l 和4 州，从而2 固定点1 3 奄和1 七同理，我们 也可以证明u 2 也固定点1 0 和1 2 奄，3 3 k l 和5 知+ l 5 1 和2 - 1 2 3 七一l 和4 七+ 1 ，4 l 和3 _ 1 故忱= 1 。 其次，证明点稳定子群a 0 0 竺d s 因为a 0 0 在丁上忠实作用，则在同构意 义下，a o o 又因为a 0 0 包含d 8 ，故a 0 0 竺& 或d 8 若4 0 0 竺& ，则a 0 0 在于蚶( o o ) 上是乒传递的，即存在0 3 2 a 0 0 ，使得忱固 定点2 0 和5 0 ，互换3 0 和4 0 如图7 所示，由忱固定点2 0 和5 0 ，而过此两点只有 两个6 - 圈，即( 0 0 ，2 0 ，5 k + 1 3 k ，1 2 k ，5 0 ，0 0 ) ，( 0 0 ，2 0 ，1 3 k ，4 3 t ，2 3 七- 1 5 0 ，0 0 ) ，则w 2 固定点4 1 和3 “从而固定点1 1 和1 七_ 1 因此忱要么固定0 l 和3 3 k ，要么对换0 1 和3 3 若 w 2 固定点0 - 和3 s 七，因为于如是点传递的，则u ：固定图中所有点这与假设矛 盾若忱对换0 l 和3 3 k ，则比对换集合 2 l ，3 z ) 和 5 。m ，) ，这是不可能的 事实上， o 奄，0 2 ，o s 七) 为a o d 不变的 故a 0 0 兰d 8 定理1 的证明 证明：由引理3 1 ，3 2 和3 3 可知定理1 成立 最后指出，我们还没有确定图于幽与氏是否同构 2 1 口 r e f e r e n c e s 参考文献 【1 】d i x o nj d a n dm o r t i m e rb ，p e r m u t a t i o ng r o u p s ，s p r i n g e r - v e r l a g ，n