（运筹学与控制论专业论文）2p2阶cayley图的正规性.pdf

v ( x ) e ( x ) a ( x ) a u t ( x 全文通用记号 有限群 子集 图 顶点集 这集 弧集 自同构群 g s x 声明 本人郑重声明：本论文的所有研究工作都是在我的导师一冯衍 全教授指导下，由本人独立完成，论文中所引用的已知结论均已 列在参考文献中未经本人许可，任何擅自更改，抄袭本论文之 内容的行为，都将承担相应的学术和法律责任 葺录 摘要 王 c a y t 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 的前正砌褒示r ( g ) 正：规予x 的念塞羁橡群a u t ( x ) 。卷关c a y t e y 爨正规性的璎究也是剐剃 起步，它是由北京大学徐明曜教授在1 9 9 5 年提出的，难式发凝于1 9 9 8 年d i s c r e t em a t h e m a t i 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 一文中【1 】 c a y l e y 潮正规往对稷多方面的研究非常重要饲魏， c i - 子集，弧 健递爨穰半赞递匿等一个自然的阉题是；给定个有限群g ，决定其所 有的难规的和非正规的c a y l e y 图然而逸是一个非常困难的问题，目前 莰知索数酶帮素数平方貔群，潋及鼯雾瓣懿爨毒c a y l e y 溪戆纛粳楼舅 外所有不连通正规c a y l e y 图已被决定，因此本义中假定c a y l e y 图都是 连通的 蹦x 的舡弧悬寿序的$ + 1 令顶点嚣组( v o ，砚，地幽) ，使得地 与q + 1 ( 1st 墨s ) 相邻且仉一l 地+ l ( 1 is8 1 ) 圈x 称之为s 一弧 传递懿，舞聚鑫霹稳群a u t ( x ) 在x 戆舢弧纂点抟递慰于弧传递爨瓣 研究，3 度藏则图一直受到图论学者的关注在1 9 4 7 华，t u t t e 证明了 每一个有限3 度对称圈是8 一正翔静，这量s 囊多秀5 ， 农本文巾我们生要考虑了妒除3 发c a y l e y 图的正规性，找到了 目录 2 两类非正规的无限族，其中一类为对称图，另一类则非对称作为一个应 用，我们分类了2 p 2 阶3 度弧传递c a y l e y 图 关键词tc a y l e y 图，正规c a y l e y 图，s 一正则图 a b s t r a c t a ，c a y l e y d e f i n e ds oc a l l e dc a y l e y g r a p h i n1 8 7 8i no r d e rt oe x p l a i n t h e g e n e r a t i n ge l e m e n t sa n dd e f i n i t i o nr e l a t i o n so fag r o u p b u tb e c a u s eo f i t ss i m p l i f i 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 d v a r i f i e s ，r e s e a r c h e r s o n g r a p ht h e o r yp a y l n o r ea n dm o r ea t t e n t i o no i li t c a y l e y 秽a p h sh a v e b e c o m ea ni m p o r t a n tr e s e a r c hf i e l do fg r o u pa n dg r a p h e s p e c i a l l yi n r e c e n tt w e n t yy e a r s ，w i t ht h ed e v e l o p m e n to fc o m p u t e r s ，p e o p l ef i n dt h a t c a y l e yg r a p h sa r eg o o dm g t h e m a t i c a lm 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 a sar e s u l t ，i tg e t sp r a c t i c a la p p l i c a t i o na n db e c o m e s m o r ea n dm o r ei m p o r t a n t f o r8c a y l e yg r a p hx = c a y ( g ，$ ，xi ss a i dt ob en o r m a li ft h e f i g h tr e g u l a rr e p r e s e n t a t i o nn ( a ) o fg i sn o r m a li nt h ea u t o m o r p h i s m g r o u pa u t ( x ) o f x t h es t u d yo ft h en o r m a l i t yo fc a y l e yg r a p h sw a s p r o p o s e db yp r o f e s s o rx u i n1 9 9 5a n dw a sf i r s tm e n t i o n e di nt h ea r t i c l e 【1 】i n l 9 9 8 t h es t u d yo ft h en o r m a l i t yo fc a y l e yg r a p h si si m p o r t a n tf o rm a n y c k s e s ，f o re x a m p l ec i - s u b s e t s ，a r c - t r a n s i t i v eg r a p h sa n dh a l f - t r a n s i t i v e g r a p h s 。an a t u r a lp r o b l e m i st h a tf o r 鑫g i v e nf i n i t eg r o u p ，h o wt od e t e r - m i n ei t sn o r m a la n dn o n n o r m a lc a y l e yg r a p h s ? i nm o s ts i t u a t i o n s ，i ti s d i f f i c u l tt od e t e r m i n et h en o r m a l i t yo fc a y l e y ( d i ) g r a p h s i nf a c tt h eo n l y g r o u p s ，f o rw h i c h t h e c o m p l e t ei n f o r m a t i o n a b o u tt h en o r m a l i t yo fc a y l e y f d i ) g r a p h si sa v a i l a b l e ，a r et h ec y c l eg r o u p so fp r i m eo r d e r 淄a n dt h e g r o u p so fo r d e rt w i c eap r i m em a n s a r c i n a g r a p h x i s a n o r d e r e d ( s + 1 ) 一t u p l e ( v o ，也l ，一1 ，口s ) o fv e r t i c e so fxs u c h t h a t 地一1 i s a d j a c e n tt ov f o r1 i s ，a n d 地一1 仉+ lf o r1 i 3 ) 是2 一 芷剿晨c a y ( a 2 ( 3 ) ， c ，嘲 ) 是正鲻的令y = e a y ( g u ) ， c ，西 ) 注意掰x = c a y ( c 3 ) ， c ，c a b ，( c a b ) 。 ) 如下定义扶g 3 ( 函剿g 2 狭 射6 ：扩h8 警# 电2 争讳2 笋j ，蕊h 2 8 + 尚譬冲簪j ，这鬟 释， 为任意蟾整数。要! | 6 势攀封娃为溅射。对警茹罨g 3 国穰y g 国，鼹 n x ( x ) 鞠( 爷) 努剩表忝。襄y 褒x 窝y 中鼹邻域，然嚣，藏计算壤 n y ( ( a 护) 6 ) = l n x ( a b j ) 1 5 ： 徽学( i 州) b 译计宁j ，学) + 1 6 警l + 学j ，蝴警( 州) 6 呼件皆什1 ， 胍( ( c 一彬) 5 ) 一【g x ( e ) r ：f 。学( 蜥) b 学i + 警j ，。警( i 十曲一1 b 孚警，o 警# 卅) b 争学j 一1 从黹。6 是x 到y 的一个同构由此可推出当p = 3 时，是3 - 正猁 的瓷p25 对，c a y ( g 3 ( 动， e ，c a b ，( 妨_ 1 ) 麓各泛劐酶获蔼， p 5 辩| a u t ( x ) | = 1 2 p 2 ；p 一3 对 a u t ( x ) 一2 33 3 出禽繇2 2 。4 ，藏 躲考0 帮( 繇) ，耘c a b ，( c a b ) 。 ) 蔗簿正鬟辩，嚣势| a u t ( g s ) ，秘c a b , ( 6 ) “ ) l = 2 ， 秘 众掰餍知在鬻祷鼢意义下，貔为8 魏簿交换释骞薅令，帮二蠢俸群 撬藕罄嚣数释酝： d 8 一。，b la 4 = 护= l ，b 一1 a b 一矿1 ) ； q 8 一( o ，b l 一1 ，b 2 = n 2 ，a b = b a 一1 ) 本节的主要内容熟证明下面的定理 定溅2 3 4 令g 为2 矿价群( p 为僚一素数) 且令s 隽g 酶3 - 元生成 第二章2 p 2 阶3 度c a y l e y 困的正规性和孤传递围的分类2 2 集且s ；s 刺，x = o a y ( g ，s ) 非正玩当z - o 当下刘之一发斑； ( 1 ) g 一墨z 2 = ( 8 酚，s 兰 。，。，6 ，且x 同约譬 3 ，酚黄8 姆 3 维立方体图； ( 2 ) g d s ，s 些 ，b a ，b a 2 或者，8 ，a - 1 ，豆x 凌毒辱节q 3 ； ( 3 ) g g 2 ( 3 ) ，s 皇 c ，曲 ，且x 同构千阶为1 8 的p a p p u s 阑； ( 4 ) g = g a ( 3 ) ，s 舅 c ，c a b ，e 8 的。 ，苴x 砖构千阶搀1 8 秘p a p p u s 固； ( 5 ) g g 3 ( p ) 且s 裂 c ，o a ，( n 6 ) 。 ，在这种情况下，c a y ( g 3 ) ， c ，曲， ( 8 够。j ；螃垒鑫臻热群始泠秀8 矿； ( 6 ) g g 3 ( p ) 加5 ，且s 豁 c ，c a b ，( c a b ) “ 。在这种情况下，c a y ( c 3 0 ) c ，c a b ，( c a b ) q ) 的奎鸯霹掬群酌阶为1 2 矿 证明令g 为助2 阶有隈群，p 为傣一索数令x = c a y ( g ，s ) 为3 度 连通c a y l e y 翻令a = a u t ( x ) 髓a l 为单位元1 在a 中的点正规化 子。显然，定瑾2 3 4 ( 1 ) 可蠢鑫题2 2 。9 拯蹬。扶秀，我爨以缓设g 是嚣 交换的如果p = 2 则i g i 一8 进而有g 为二面体群d 8 或者为四元数群 蕊注慧弱镳哭有个对会，置镣意静4 狳元帮椎一静对台不髓够生壤 q k 这糖说明枢q s 上没有遵通的3 度c a y l e y 匿，从而我们有g = ) 彦 注意到自同构群a u t ( d s ) 在对合集弘，氓6 0 2 ，6 口3 ) 上传递，我们不妨设 扩s 残6 s 。注意巍映瓣8 8 _ 。，b 6 羁软射8 一a 一，b h 如诱 导出d 8 的自间构由此可报出如果a 2 s ，由x 的连通性我们有s 觎 铲，b ，酝 ；翔槊矿g 最类鬣瓣我键有s 垒氇b a ，魄2 交卷撬口，珏。 ，耪 见c a y ( d a ，p ，b a ，b a 2 ) ) 星c y ( d s ，p ，a ，n “) ) 笺q 3 ，即兰维立方俸图因 为q 3 是2 、藏则的鼠j a u t ( d s ，袖，a ，a - i ) ) i = l a u t ( d a ，伯，b a ，b 舻) ) l = 2 ， 瘗惫糕2 2 4 ，g 8 y ( d s ，b a ，6 扩 鞠c a y ( d a ， 6 ，8 ，8 。 ) 都是正授的， 第二章劬2 阶3 度c a y l e y 制的正规性和弧传递圈的分类 2 3 鄢定理( 2 ) 中情况令x = c a y ( d s ， 舻，b ，阮) ) 遇过1 ，a 2 和b 有一个 靠曝，但是避进1 ，b 释k 龆没有4 圈。盎此我们易褥 a l l 一2 ，遣搜 c a y ( d s ， 扩，b ，b a ) 魑正规的 褒在我# ：鞭设g 蹙 # 交换2 矿一群，这墨p 努素数襄p 3 ，获焉， g = a l ( ，g z ( p ) 或者g 3 0 ) 定理可由引理2 3 1 ，2 3 2 和2 3 3 推出， 出 2 42 p 2 阶3 魔c a y l e y 豳的弧传递豳分类 刘愿上一节中螅绩果，我们绘磁了2 p 2 酚3 发3 _ 正则c a y l e y 匮蛇 分类，避里1ss 5 且p 为任一素数 | 耋论2 4 1 令落秀泠鸯2 p 2 妁群，这里尹舞任一素数。令s 为0 螃五 兄生成柴且s = s 如果x = c a y ( g ，s ) 是对称的，则x 是l ，2 一或 者3 一藏硝的进而有， ( 1 ) x 是l 一- 茈j l l 的墨且仅当x 焉构于c a y ( g l ( 砧， 6 ，b a ，b a ) ) ，这里p 为常数且满足p 一1 具有因子3 ，且k 为舀中阶为3 的元进而， c a y i e y 匿c a y ( g l 翻，p ，b a ，b a - k ) 与k 在三娉选褥无关 ( 2 ) x 是2 一点则的当且仅巍x 同构于三维立方体困口3 ，或c a y l e y 圜 c a y ( c 3 秭， c ，c a b ，( c a b ) 。 ) ，这里p 为素数且p 5 一 f 3 ) x 是3 一点则的当且经当x 同扮于1 8 阶p a p p u s 图 证明令x c a y ( g ，s ) 为2 p 2 阶有限群上的3 度连i 匝对称溺由定 理2 3 + 4 ，凌餐翔簸了x = ( 岛f p ) ； c ，幻，西) - 1 3 ) 终爨毒缒 # 正瓣 c a y l e y 图是对称的，且所有这些对称图在推论( 2 ) 和( 3 ) 中已经列出 执雨，我们可戳假设x 是正规的。西为x 燕对称静，毒命疆2 2 4 ， 第= 章妒阶3 度c a y l e y 图的正规性和弧传递图的分类 2 4 a 1 = a u t ( g ，国程s 主簧魏囊手s 至少鑫有一夸麓会，翔s 一定是 戗禽三个对合如果p = 2 刘i g l = 8 由命题2 2 1 0 ，x 鲁q ，属于 推论( 2 ) 中的情况令p 3 在这种情况下，g 一定为日e 交换的，因 为稳三个对合生成鳃交换群阶楚雾为8 出此可推出g g t ，g 2 ) 我者g 3 回注激到g 3 锄幂鼹由三夸对含搬成，赠g ( b 鲡荣 g g 1 0 ) ，由命题2 2 6 ，我们得到推论中( 1 ) 现在我们令g = g 2 ( p ) 由 引理2 3 2 中的证明，x 掣a a y ( g 2 ， c ，c 6 ) 且由引璩2 3 3 中的诞 鹾，c a y ( g 2 国， e ，c a ，嘲) 簧c a y ( c 3 ) ，奴c a b ，( c a b ) o 封，穰于蓑论( 2 ) 朔( 3 ) 的情况 a 参考文献 【1 】x um y ，a u t o m o r p h i s mg r o u p ss a di s o m o r p h i s m so fc a y l e yd i g r a p h s d i s c r e t em a t h e m a t i c s ，1 8 2 ( 1 9 9 8 ) ，3 0 9 - 3 1 9 【2 】a l s p a c hb ，p o i n t s y m m e t r i cg r a p h sa n dd i g r a p h so fp r i m eo r d e ra n dt r a n s i t i v ep e r m u t a t i o ng r o u p so fp r i m e d e g r e e ，zc o m b i n t h e o r y , 1 5 ( 1 9 t 3 ) ， 1 2 - 1 7 鞠d us f ，w a n gr 。j 。x um y ，o nt h en o r m a l i t yo fc a y l e yd i g r a p h s o fo r d e rt w i c eap r i m e ，a u s t r a l a s i a nj o u r n a l0 ，c o m b i n a t o r i e s ，1 8 ( 1 9 9 8 ) ， 2 2 矗2 3 4 ， 【4 f h a r a r y , g r a p ht h e o r e y ，a d d i s o n w e s l e y , r e s d i n g ，m a ，1 9 6 9 【5 lp r a e g e rc e ，f i n i t en o r m a le d g e - t r s a s i t i v eg r a p h s ，b u l l a u s t r a l m a t h ， b ，6 0 ( 1 9 9 9 ) ，2 0 7 - 2 2 0 问l u z p x um y ，o nt h en o r m a l i t yo fc a y l e yg r a p h so fo r d e r p q ，a u s + t r a t a s c o m b i n ，2 7 ( 2 0 0 3 ) ，8 1 - 9 3 。 【7 jw a n gc q ，w a n gd j x um y ，o nn o r m a lc a y l e yg r a p h so ff i n i t e g r o u p s ，s c i e n c e 漉c h i n a ( a 支2 a ( 1 9 9 s ) ，1 3 1 1 3 9 ， 8 】n n gx g ，l ic h ，w a n gd j 舭x um y ，o nc u b i cc a y l e yg r a p h so f f i n i t es i m p l eg r o u p s ，d i s c r e t em a t h e m a t i c s , 2 4 4 ( 2 0 0 2 ) ，6 7 - 7 5 。 1 9 】l ic h ，o ni s o m o r p h i s m so fc o n n e c t e dc a y i 可g r a p h si l l ，b u l l a u s t r a l ， m a t h s o c ，5 8 ( 1 9 9 8 ) ，1 3 7 - 1 4 5 【t 0 1f e n gy 。q ，w a n gr j 。x um ya u t o m o r p h i s mg r o u p s o f2 - v a l e n tc o n - n e c t e dg 8 y l e yd 酶a p h so i lr e g u l a rp - g r o u p s ，g r a p h sa n dc o m b i n a t o r i c s , 1 8 ( 2 0 0 2 ) ，2 5 3 - 2 5 7 ， 【1 1 】b a l ky g ，f c n gy q s i mh s ，t h en o r m a l i t yo fc a y l e yg r a p h so f 参考文献 2 6 f i n i t ea b e l i a n g r o u p sw i t hv a l e n c y5 s y s t e m ss c i e n c ea n dm a t h e m 8 t l ； s c i e n c e s ，l a ( 2 0 0 0 ) ，4 2 5 - 4 3 1 【1 2 】b a l ky g ，f e n gy q ，s i mh s x um y ，o nt h en o r m a l i t yo fc a y l e y g r a p h so fa b e l i a ng r o u p s ，a l g e b r ac o l l o q u i u m ，5 ( 1 0 9 8 ) ，2 9 7 - 3 0 4 ， 瑟3 lf e n gy ，q ，k w a kj 。h 。w a n gr j a u t o m o r p h i s mg r o u p so f4 - v a l e n t c o n n e c t e dc s y l e yg r a p h so f p - g r o u p s ，c h i n a n n m a t h ，2 2 b ( 2 0 0 1 ) ，2 8 1 。 2 8 6 f 1 4 1f e n gy q 。，w a n gd j 。c h e nj 。l 。，af a m i l yo fn o n - n o r m a lc a y l e yd i - g r a p h s ， e 掘m a t h e m a t i c ss i n i c a , n e ws $ 栽e 焉l r ( 2 0 0 1 ) ，1 4 7 - 1 5 2 。 f 1 5 jd j o k o v 记d # m i l l e rg l ，r e g u l a rg r o u p so fa u t o m o r p h i s m so fc u b i c g r a p h s ，工c o m b i n t h e o r yb ，2 9 ( 1 9 8 0 ) ，1 9 良2 3 0 【l 锈c o n d e r m d e p r a e g e rc ，e ，r e m a r k so np a t h - t r a n s i t i v i t yo nf i n i t e g r a p h s ，e u r o p ，j , c o m b i n t ) | 1 7 ( 1 9 9 6 ) ，3 7 l - 3 7 8 1 1 7 f r u c h tr ，ao n e - r e g u l a rg r a p ho fd e g r e et h r e e ，c a n a d j m a t h ，4 ( 1 9 5 2 ) ， 2 4 0 - 2 4 7 【1 8 m i l l e rr c + ，t h e t r i v m e n t s y m m e t r i cg r a p h so f 盛t h 鲢m o s ts i x ， c o m b i n t h e o r yb ，1 0 ( 1 9 7 1 ) ，1 6 3 - 1 8 2 【1 9 1c h e n gy o x l e yj ，o nw e a k l ys y m m e t r i cs y m m e t r i cg r a p h so fo r d e r t w i c e & p r i m e ，j c o m b i n ，t h e o r yb ，4 2 ( 1 9 8 7 ) ，1 9 6 - 2 1 1 。 渊t u t t ew t ，af a m i i yo fc u b i cg r a p h s ，p r o c c a m b r p h i l o s o p h 踟， 4 3 ( 1 9 4 7 ) ，4 5 9 4 7 4 2 1 】t u t t ew t ，o nt h es y m m e t r