论文部分内容阅读
设G为有限群，S是G的不含单位元的子集.我们如下定义群G关于其子集S的Gayley有向图Cay(G，S)：其顶点集合为G，而其边集合为{(g，sg)|g∈G，s∈S}.若S-1=S，则Cay(G，S)叫做Cayley图并且它是无向图.此时，我们把一条无向边{g，h}等同于两条有向边(g，h)和(h，g).一个Cayley(有向)图Cay(G，S)是连通的当且仅当G=〈S)，也就是S生成G.由于群G的右正则表示R(G)作为Aut(Cay(G，S))的一个子群，正则地作用于Cay(G，S)的顶点集合上，因而Cayley图Cay(G，S)为点传递图.
一个Caylcy(有向)图Cay(G，S)称之为正规的，如果G的右正则表示R(G)为Cay(G，S)的全自同构群Aut(Cay(G，S))的一个正规子群.Cayley(有向)图正规性的概念是由北京大学徐明曜教授提出的，参见文献DiscreteMathematics，182(1998)，309-319.它对Caylcy图对称性等的研究都起着很重要的作用.本文工作就是围绕Cayley(有向)图的正规性展开的.我们主要考虑了4p(p为素数)阶小度数Cayley(有向)图的正规性.首先，我们完全决定了4p阶群上的2度Cayley有向图的正规性，证明了一个4p阶群G上的关于其2元子集S的Caylcy有向图X=Cay(G，S)是正规的，除非X≌(→C)2p[2K1]，Aut(X)≌Z2wrZ2p，且G=Z4p=〈e〉，S={e，e2p+1}或G=Z2p×Z2=〈e〉×〈f〉，S={e，ef}.另外，我们还完全决定了4p阶非二面体群上的4度Cayley图的正规性.作为所得结果的应用，我们构造了一个4度1-正则图的无限族，这些图都是群〈a，b|ap=b4=1，b-1ab=ar，r2≡-1(modp)〉上的非正规Cayley图.