论文部分内容阅读
设Γ为一个图,Aut(Γ)为Γ的全体自同构群。如果存在X≤Aut(Γ)使得X在Γ的边集EΓ上传递,则称Γ为X-边传递图。设G为一个群,一个图Γ称为群G上的Cayley图,如果存在G的一个非空子集S,使得S()G\{1},且顶点x与y邻接当且仅当yx-1∈S.这个Cayley图记为Cay(G,S).特别地,二面体群上的Cayley图称为二面体图。进一步,如果Cayley图Γ=Cay(G,S)为X-边传递图使得G为X的正规子群,则称Γ为X-正规边传递Cayley图。
边传递Cayley图,包括正规边传递Cayley图是代数图论活跃的课题之一,受到了众多学者的关注,参见文献[11,12,15,16]及其中的参考文献。本文主要研究正规边传递二面体图。我们完全刻画了正规边传递二面体图的所有可能的度数,并且构造了具有这些度数的图类。
下面的定理1确定了正规边传递二面体图的度数。
定理1.设Γ=Cay(G,S)是连通的X-正规边传递二面体图,且Val(Γ)≥2,G()D2n≤AutΓ,这里n=p1r1p2r2…p1r1是n的标准分解式。则有
(1)如果t=1,则有k=p1r1或者k|φ(p1r1)其中(φ是Euler函数);反过来,对于每一个满足这些条件的k,都存在一个度数为k的连通的正规边传递二面体图;
(2)如果t≥2,则有[k1,k2…kt]k且k≤k1k2…kt.其中ki=p1r1或者k1|φ(pir1)(i=1,2,…,t).
定理2给出了具有可能度数的正规边传递二面体图的构造。
定理2.设G=<α,b|αn=b2=1,αb=α-1>()D2n为二面体群,其中n=pr,p是素数。
(1)若p是奇素数,令H1=<σcτd>,其中p不整除c且p-1整除d,且令H2=<σcτpr-α-1e),其中p不整除c,e是p-1的非平凡因子(e整除p-1但e≠1,p-1),且1≤α≤r-1.对于i=1,2,我们记Si=bH1.
(2)若p=2,令H3=<σ2β,τcτ0>,其中2不整除c,1≤β≤r且τ0∈R满足ατ0=α-1.记S3=6H3.记Γi=Cay(G,S)是Cayley图(i=1,2,3).则Γ是连通的正规边传递二面体图,且
Val(Γ1)=pr,Val(Γ2)=e/pα(p-1),Val(Γ3)=2r-β+1.
本文第二章和第三章分别介绍了群论和图论的相关概念和性质,第四章证明了本文的主要结果。