奇图Ok及其非Cayley性.pdf

奇图Ok(k)是一类高度对称的、具有独特结构的简单无向图例如O被发现是点传递图中既非H a m i l t o n图也非C a y l e y图的典型例子该文给出了一些关于奇图的新结果,特别是在奇图中找到了非C a y l e y高弧传递图的无限族关键词:奇图;弧传递图;C a y l e y图;对称群中图分类号:O 文献标志码:A代数图论的一个重要研究领域是通过简单图的自同构群的传递性来描述图的对称性,其中最基本也是最主要的一种传递性是点传递性点传递图中的一个大类是C a y l e y图,它几乎是点传递图的全部因此寻找更多非C a y l e y点传递图的例子是很有意义的奇图Ok是具有高度对称性的图(不仅是点传递的,还是高弧传递的),同时也很奇特,比如它有非H a m i l t o n图和非C a y l e y图的例子但目前国内外关于奇图Ok的研究结果还比较少本文证明所有的奇数度奇图和绝大多数偶数度奇图是非C a y l e y的,由此得到了非C a y l e y高弧传递图的无限族本文使用的定义和记号都是通用的未加说明的术语或代数图论中的浅显结论均出自文献,本文中的图均指简单无向图预备知识引理对任意正整数n,阶乘n!的因子中的个数为ini,其中x 表示实数x的整数部分推论对任意正整数n,阶乘n!的因子中的个数n,其中等式成立当且仅当n是的幂定义群G作用在集合上,记作G,是指G中的每个元素g都给出上的一个变换g,且满足(),;()(g)hg h,g,hG并称集合G gG|g,为该作用的核如果G是平凡的,则称该作用是忠实的如果对任意,都存在gG使得g,则称该作用是传递的易知G是G的正规子群,且商群G/G可嵌入的对称群S y m()设,称集合G gG|g为G关于的点稳定子,并记G gG|g,G()gG|g,这三者都是G的子群,且G()是G的正规子群称集合G g|gG 为所在的G 轨道,并记g g|,G g|,gG这三者都是的子集,且有轨道公式|G|GG|收稿日期:基金项目:国家自然科学基金(,)作者简介:徐尚进,男,安徽庐江人,教授,博士,博士生导师,研究方向:代数图论Em a i l:x u s j i n q q c o m南 宁 师 范 大 学 学 报(自 然 科 学 版)第 卷例设,n,kn对的任意两个k元有序组(i,i,ik)和(j,j,jk),上的置换iiikjjjk使得(i,i,ik)(j,j,jk),故S y m()在k元有序组集合上的作用是传递的,也称作用S y m()是k重传递的例设H是群G的子群,记GH 为H的右陪集的全体,则G在GH 上有右乘作用P,它定义为(Hx)P(g)H(x g),x,gG令P(G)P(g)|gG,则群作用P(G)GH 是传递的,且P(G)关于H的点稳定子恰为P(H);P(G)GH是忠实的当且仅当H在G中的核HG gGg Hg是平凡的定义设群作用G是忠实的,若对任意都有G,则称G在上是半正则的,并称G中的非单位元为强正则元;若G还在上传递,则称G是正则的性质若群作用G是半正则的,则G的任一非单位元g在中都无不动点,进一步地,g在上可分解为|o(g)个长都为o(g)的轮换之积定义设群作用G是传递的若存在子集满足|,并对任意gG都有g或g,则称为G的非本原块若G无非本原块,则称该作用是本原的性质设群作用G是传递的,则G是本原的当且仅当对任意,G都是G的极大子群定义 图的顶点集和边集分别记作V()和E()若是有限图,即V()和E()都是有限集,则称的顶点数称为的阶,记作|中与顶点v有边相连的顶点的全体称为v的邻域,记作N(v),并称d e g(v)|N(v)|为v的度各顶点的度都相等的图称为正则图图的每条无向边v,u都对应着两条有向边(v,u)和(u,v),称为的弧的弧的全体记作A r c()定义 设是图的顶点集V()上的一个置换,如果顶点u与v相邻时u与v也相邻,则称为的一个自同构图的自同构的全体构成一个群,称为的全自同构群,记作A u t()A u t()关于顶点v的点稳定子A u t()v可简称为的点稳定子易知A u t()V()是忠实的如果A u t()V()是传递(本原)的,则称是点传递(点本原)的如果A u t()在A r c()上的诱导作用是传递的,则称是弧传递(或对称)的弧传递图都是点传递图不难证明,若图是度点本原的,则要么是弧传递图,要么A u t()V()正则由于图自同构保持边仍变到边,而边与边以及边与顶点之间的邻接情况又决定了图的结构,即图论性质因此点传递图各顶点的图论性质彼此是一样的,这就是图的对称性显然弧传递图的对称性强于点传递图定义 设(v,v,vs)是图的一个顶点序列,如果对任意is,vi 与vi都相邻,并且对任意is都有vi vi,则称该序列为的一条s 弧,记作v图的s 弧的全体记作A r cs()注意,s 弧与s 路是不同的概念,s 弧上的顶点允许重复,如图所示只含一个顶点的序列可视为弧图第期徐尚进:奇图Ok及其非C a y l e y性定义 设v,u A r cs(),若uivi,i,s,则称u 为v 的一个后继性质 设是连通的正则图且其度d,vA r cs(),则与vs相邻的顶点除vs 外还有d个,分别记作v()s,v(d)s 此时s 弧v(i)(v,vs,v(i)s),id是 v的所有后继(见图)图引理 设连通图的每个顶点的度数都不小于则对任意v,uA r cs(),中存在一列s 弧v(i),i,m,使得v()v,v(m)u,且v(i)是v(i)的后继,i,m定义 如果图的全自同构群A u t()在A r cs()上诱导的作用是传递的,则称为s 弧传递图如果图是s 弧传递的但不是(s)弧传递的,则称为s 传递图前面定义的点传递图即为 弧传递图,而弧传递图即为 传递图当s时,称s 弧传递图称为高弧传递图,它们是具有极高对称性的图定义 设是连通的n阶s 传递图(s),且其度d,v(v,v,vs)是的一条s 弧对r,s,记A A u t()关于(sr)弧(v,v,vsr)的稳定子群为Fr称A的子群序列AFsFs FF为 v的稳定子序列定义 设k,以集合,k 的k元子集为顶点,并规定两个顶点u与v相邻当且仅当uv,所得到的图称为奇图,记作Ok性质()A u t(Ok)有子群Sk()Ok是kk阶k度弧传递图()Ok是连通的()设k,则Ok的任一条 路有且仅有一个 圈例 如图所示,奇图O有H a m i l t o n圈,而O有H a m i l t o n路,但没有H a m i l t o n圈可以证明O也没有H a m i l t o n圈图奇图O和O有关引理引理设群G的两子群H与K互补,即GHK且HK,则H的每个非单位元与K的每个元素都不共轭南 宁 师 范 大 学 学 报(自 然 科 学 版)第 卷引理设p是素数,则对任意整数k,Sp都不含p k阶元引理设GSn(n),k,kn,则G是G的一个极大子群,进而G关于G的右乘置换表示是本原的证明设GHG,HG,则不失一般性,可设,并由|kn可得()故存在i()若ii,则由i()知对换(i i)G()GH此时取(i i)H,可使,ii若ii,则直接取也使上式成立总之,存在对换(i)G()GH,进而有(i)(i)H下证对任意j有(j)H事实上,当j时有(j)GH;当j且ji时,由(i j)GH可得(j)(i j)(i)(i j)H从而H(,j)|jnG引理设GSk,k,k,则对G的任一阶元g,存在G使得g g G证明令 k,k,k,则G S y m()S y m()设g(ii)(ii)(ij ij),其中jk若k是奇数,或kj,则G中有阶元g()()(j,j),这时G中置换iiij ijj j可使gg G若k是偶数,且kj,则G中有阶元g()()(k,k)(j,j),这时G中置换iiik ik ij ijkkjj可使gg G引理的边数为|E()|vV()d e g(v)特别地,的奇数度顶点必为偶数个对于图,A A u t()关于的顶点v的点稳定子记作Av引理设是点传递图,则|AAv|,且A关于子群Av的右乘置换表示P(A)AAv是忠实的证明由轨道公式立得|AAv|因AV()是忠实的,而P(A)AAv 与AV()置换同构,故P(A)AAv也是忠实的引理设是k度点传递图,则Av可诱导N(v)上的作用,且有()|Av|k!|Av|()对任意uN(v)有|Av|k!(k)!|AvAu|证明()注意到Av/Av可嵌入S y m(N(v),即得|Av/Av|k!()当uN(v)时也有vN(u),故Av和Au均为Av uAvAu的正规子群,于是由群的同构定理得AvAvAuAvAuAuAv uAu但Av u/AuN(u)v是忠实的,又得|AvAvAu|Av uAu|(k)!从而有|Av|k!|Av|k!|AvAvAu|AvAu|k!(k)!|AvAu|引理设是连通的正则图且其度d,则是s 弧传递图当且仅当存在,d A u t(),使得viv(i),i,d第期徐尚进:奇图Ok及其非C a y l e y性引理设s,则是s 弧传递图当且仅当A A u t()A r cs()是传递的,并且A关于(s)弧(v,v,vs)的稳定子群FAvvvs 在N(vs)vs 上传递证明“”显然AA r cs()是传递的任取vs,vsN(vs)vs ,有s 弧v(v,v,vs,vs)和v(v,v,vs,vs)因是s 弧传递的,故存在A使得vv,此时有Avvvs,vv“”由条件知,存在A使得(v,vs,vs)(v,v,vs)此时vs和(v(i)s)都在N(vs)vs 中(见图),i,k于是存在iAvvvs 使得vis(v(i)s)由此推出vi(v,v,vs,vs)i(v,v,vs,vis)(v,v,vs,v(i)s)v(i)进而由引理知是s 弧传递图图推论 弧传递图是s 弧传递的(s)当且仅当对任意t,s,A A u t()关于t 弧(v,v,vt)的稳定子群FstAvvvt在N(vt)vt 上传递推论 设ls如果经过度数不小于的无向图的一条(s)弧有唯一的l 圈,则不是s 弧传递图证明假设是s 弧传递图,则由引理,A A u t()A r cs()是传递的,并且A关于(s)弧(v,v,vs)的稳定子群Avvvs 在N(vs)vs 上传递此时经过弧(v,v,vs)也有唯一的l 圈于是弧稳定子群Avvvs 必点不动这个l 圈,但圈上却有顶点含于N(vs)vs 这与Avvvs 在N(vs)vs 上传递矛盾关于奇图还有以下一些性质引理 当k是奇数时Ok的阶是偶数当k是偶数时,Ok的阶是奇数当且仅当k是的幂引理()A u t(Ok)Sk()若p是k的素因子,则Ok的p阶自同构必不是强正则元证明()易见OK,故A u t(O)S图当k时,仍令A A u t(Ok),并先证AvAu,其中v,uE(Ok)事实上,对任意AvAu,点不动N(v)N(u),因此也点不动路v,v,u,u (见图)和经过该路的唯一圈(性质)再由Ok的连通性,即推出再由引理()和引理得|Av|k!(k)!,于是有|A|Av|kkk!(k)!(k)!最后由性质(),即推出A u t(Ok)Sk()假设A u t(Ok)存在p阶强正则元,则由性质,在V(Ok)中无不动点,并可分解为|Ok|p个不相交的p轮换之积于是p|(|Ok|,k)由|Ok|kpkp得|Ok|pkp,且有sj(ijijij p)取Ok的顶点v tjijijij p,它明显是的一个不动顶点,这与是强正则元矛盾关于如何判断一个图是否为C a y l e y图,有以下结果引理 图是C a y l e y图当且仅当A u t()包含正则作用在顶点集V()上的子群推论 设是图()若是点传递图,则同构于C a y l e y图当且仅当的点稳定子在A u t()中有补子群()若A u t()不含|阶子群,则不是C a y l e y图例 奇图O的阶为,而A u t(O)S注意到 阶群必是循环的,但S不含 阶元(引理),故S不含 阶子群,从而O不是C a y l e y图南 宁 师 范 大 学 学 报(自 然 科 学 版)第 卷主要结果定理对任意k,奇图Ok都是点本原图证明由引理 及引理即得定理对任意k,奇图Ok都是 传递的,其弧稳定子序列是A u t(Ok)Sk FSkSk FSk Sk FSk Sk FSk Sk 定理设k,若Ok的阶与k不互素,则Ok不是C a y l e y图证明假设Ok是C a y l e y图,则由引理,A u t(Ok)包含正则作用在V(Ok)上的|Ok|阶子群,记为G由|Ok|与k不互素可知,|Ok|与k有公共素因子p,于是G中(进而A u t(Ok)中)有p阶强正则元,这与引理()矛盾推论奇数度奇图都不是C a y l e y图证明根据引理,当k为奇数时Ok的阶是偶数,故由定理可得结论定理设k,若k不是的幂,则Ok不是C a y l e y图证明只需考虑k是偶数的情况假设Ok是C a y l e y图,则根据推论 (),A A u t(Ok)关于顶点v的点稳定子Av在A中有补子群,设为G再根据引理,G的每个非单位元与Av的每个元素都不共轭然而由引理 ,|G|Ok|是偶数,于是G有阶元且它与Av中的阶元共轭(见引理)矛盾定理的逆命题不成立,即当k是的幂时,Ok仍可能不是C a y l e y图,例如O(见例)例奇图O 的阶为 ,与 不互素,故由定理 知O 不是C a y l e y图最后提出一个猜想:对任意k,奇图Ok都不是C a y l e y图参考文献:徐明曜有限群导引:上册M版北京:科学出版社,徐明曜,黄建华,李慧陵,等有限群导引:下册M版北京:科学出版社,B i g g sN A l g e b r a i cG r a p hT h e o r yM C a m b r i d g e:C a m b r i d g eU n i v e r s i t yP r e s s,徐尚进圈空间及其应用J南宁师范大学学报(自然科学版),():徐尚进有限群的同图类J南宁师范大学学报(自然科学版),():徐尚进有限传递图的偶圈对边集J南宁师范大学学报(自然科学版),():G o d s i lCD M o r eo d dg r a p ht h e o r yJ D i s c r e t eM a t h,:L iCH,JJL,L uZP T w o a r c t r a n s i t i v eg r a p h so fo d do r d e r I IJE u r o p e a nJC o m b i n,:O d dG r a p h sOka n dT h e i rN o n C a y l e yP r o p e r t yXUS h a n g j i n(G u a n g x iU n i v e r s i t y,S c h o o l o fM a t h e m a t i c sa n dI n f o r m a t i o nS c i e n c e,N a n n i n g ,C h i n a)A b s t r a c t:T h eo d dg r a p h sOk(k)a r e a c l a s so f s i m p l eu n d i r e c t e dg r a p h sw i t hs p e c i a l s t r u c t u r et h a t a r eh i g h l ys y mm e t r i c F o re x a m p l e,t h ec u b i co d dg r a p hOt u r n so u t t ob eat y p i c a l e x a m p l eo fv e r t e x t r a n s i t i v eg r a p h s t h a t i sn e i t h e rH a m i l t o n i a nn o rC a y l e y T h i sp a p e rg i v e ss e v e r a ln e wr e s u l t sa b o u to d d g r a p h s,e s p e c i a l l y,a ni n fin i t ef a m i l y o f n o n C a y l e y h i g h a r c t r a n s i t i v e g r a p h sa r ed i s c o v e r e d i no d dg r a p h s K e yw o r d s:o d dg r a p h;a r c t r a n s i t i v eg r a p h;C a y l e yg r a p h;s y mm e t r i cg r o u p 责任编辑:班秀和 责任编辑:彭喻振