具有小度数的1-正则Cayley有向图

居冉, 李玟, 李靖建

(广西大学 数学与信息科学院, 广西 南宁 530004)

1 引言及主要结果

本文中所有的图都假定为有限简单连通图。

设Γ是一个图,图Γ的顶点集、边集、全自同构群分别记为V(Γ)、E(Γ)、Aut(Γ)。设X≤Aut(Γ),若X在图Γ的顶点集、边集、弧集的作用是传递的,则称图Γ是X-点传递的、X-边传递的、X-弧传递的,在此基础上,若X=Aut(Γ),则称图Γ是点传递的、边传递的、弧传递的。令s为正整数,图Γ中的一个s-弧是指Γ中(s+1)个顶点的序列(v0,v1,…,vs)满足:当0≤i≤s-1时,vi和vi+1相邻,且对任意1≤i≤s-1都有vi-1≠vi+1。如果Γ至少有一个s-弧,且X传递地作用在Γ的顶点集和s-弧集上,则称图Γ是(X,s)-弧传递的。如果X作用在其s-弧集上正则,则称图Γ是(X,s)-正则的。如果X=Aut(Γ),则称图Γ为s-正则的。设Γ是一个有向图,v∈V(Γ)。本文称以v为起点的有向边的个数为v的出度,记作d+(v);而称以v为终点的有向边的个数为v的入度,记作d-(v)。本文中定义图Γ的度数Val(Γ)=d+(v)。

设G是有限群,S是G的不含单位元的子集。群G关于子集S的Cayley图定义为以群G中的元素为顶点和以{(a,b)|a,b∈G,ba-1∈S}为边集的图,记作Cay(G,S)。由定义可知,一个Cayley图有度数|S|,Cay(G,S)连通当且仅当G=〈S〉。本文称Cayley图是正规的,如果G在Aut(Cay(G,S))中正规。对于非正规Cayley图Γ,若存在Aut(Γ)的一个正规子群N,其作用在顶点集合V(Γ)上半正则且恰好有2条轨道,则称图Γ是双正规的。令CoreX(G)∶=∩x∈XGx,对于G≤X≤Aut(Γ),若CoreX(G)=1,则称Cayley图Cay(G,S)无核。

设G是有限群,S是G的(可以包含单位元的)子集。群G关于子集S的Bi-Cayley图定义为以G×{0,1} 为顶点集和以{{(g,0),(sg,1)}|g∈G,s∈S}为边集的图,记作BCay(G,S)。

定理1设Γ=Cay(G,S) 是一个d度(X,1)-正则Cayley有向图,d=3,4,5,6。设G

①G=N,X≤G×|Aut(G,S)且X1≤Aut(G,S);

② |G∶N|=2且1∈D⊂N,Γ≅BCay(N,D);

③ |G∶N|≥3,要么ΓN是一个有向圈,要么ΓN是例1至例3中的一个,特别地,当Val(Γ)=Val(ΓN)时,在同构意义下,Γ是例2、3中的图。

1 预备知识

设X为有限群,H为X的一个无核子群,X右乘作用在集合[X∶H]∶={Hx|x∈X}上忠实。定义陪集图Γ=Cos(X,H,HgH),其顶点集为[X∶H],边集为{(Hx,Hdx)|d∈HgH}。由定义容易得出,如果〈H,g〉=X,则Γ连通。令α=H,β=Hg,则点稳定子群Xα=H,Xβ=Hg,弧稳定子群Xαβ=Xα∩Xβ=H∩Hg。

令Γ是一个X-点传递图,N是X的正规子群,VN表示N作用在V(Γ)上的轨道集合。定义由N诱导的Γ的正规商图ΓN其顶点集为VN,若存在a∈A且b∈B在原图中相邻,则两顶点A,B∈VN在ΓN中相邻。用Val(Γ)表示Γ的度,如果Val(Γ)=Val(ΓN),则称Γ为ΓN的正规覆盖。考虑XA=NXα,其中A∈V(ΓN),α∈A,因此(X/N)A≅XA/N≅Xα。本文有如下性质:

性质1(X/N)A≅XA/N≅Xα,其中A∈V(ΓN),α∈A。

关于弧传递图,本文有如下引理:

引理1[12]令Γ=Cay(G,S)为连通(X,1)-正则Cayley有向图,其中G

引理2[13]Sn的任意2个同构的正则子群在Sn中共轭。

下面本文给出一些有向图的例子。

例2定义x1=(4,6,5),x2=(3,6,5),x3=(3,6,4),x4=(3,6,5,4),x5=(3,4,6,5),x6=(3,5,6,4),x7=(2,6,4,5),x8=(2,6,4,5,3),x9=(2,6,3,4),x10=(2,6,5,3,4),a=(1,2,3,4,5,6)。令H=〈a〉,Xi=〈a,xi〉,Γi=Cos(Xi,H,xi),其中i=1,2,…,10。通过计算得H≅Z6,|H:H∩Hxi|=6,此时Γi是一个Xi-弧传递6度图。令Si={σ∈HxiH|1σ=1},Gi=〈Si〉。计算可得:

S1={(4,6,5),(3,4,5,6),(3,5,4),(2,3,4,5),(2,4,3),(2,5,3,6,4)},

S2={(3,6,5),(2,3,4)(5,6),(2,3,5,4,6),(2,5,4),(2,5)(3,4,6),(2,6,3)},

S3={(3,6,4),(2,3)(4,5,6),(2,4,3,5,6),(2,4,5)(3,6),(2,5,3),(2,6,5)},

S4={(4,5,6),(3,4,5),(3,6,5,4),(2,3,4),(2,4,6,3,5),(2,5,4,3)},

S5={(3,4,6,5),(2,3,4,6,5),(2,3,5,4),(2,3,5)(4,6),(2,3,6,5,4),(2,4)(3,6,5)},

S6={(3,5,6,4),(2,4,5,3),(2,4,5,6,3),(2,4)(3,5,6),(2,5,6,4,3),(2,5,3)(4,6)},

S7={(2,3,6,4),(2,3,6,4,5),(2,4,6,5),(2,4,3,6,5),(2,4,3,6),(2,6,4,5)},

S8={(3,5,6),(2,3,6),(2,4,3)(5,6),(2,4,5),(2,5)(3,6,4),(2,6,4,5,3)},

S9={(2,4,6,3),(2,5,4,6,3),(2,5,6,4),(2,5,4,6),(2,5,6,3,4),(2,6,3,4)},

S10={(3,4,6),(2,3)(4,6,5),(2,3,5),(2,5,6),(2,5,4)(3,6),(2,6,5,3,4)},

则Gi=〈Si〉≅S5,Xi=〈H,xi〉≅S6。易知Gi作用在V(Γi)上正则,因此Γi≅Cay(Gi,Si),特别地,Γi是一个6度(Xi,1)-正则Cayley有向图。

例3令m=(1,2,3)(4,5,6),n=(1,6)(2,5)(3,4),x1=(3,6,5),x2=(2,6,5)(3,4),x3=(2,6)(3,5,4)。令H=〈m,n〉,Xi=〈m,n,xi〉,Γi=Cos(Xi,H,xi),其中i=1,2,3。通过计算得H≅S3,|H:H∩Hxi|=6,此时Γi是一个Xi-弧传递6度图。令Si={σ∈HxiH|1σ=1},Gi=〈Si〉。计算可得:

S1={(3,6,5),(2,3,5),(2,5,4),(2,5)(3,6,4),(2,6,5,4,3),(2,6,4)(3,5)},

S2={(3,4,5),(2,3,6,4,5),(2,4,3),(2,4)(3,6,5),(2,6,4),(2,6,5)(3,4)},

S3={(3,6,4),(2,3,5,6,4),(2,5,6),(2,5,4)(3,6),(2,6,3),(2,6)(3,5,4)},

则Gi=〈Si〉≅S5,Xi=〈H,xi〉≅S6。易知Gi作用在V(Γi)上正则,因此Γi≅Cay(Gi,Si),特别地,Γi是一个6度(Xi,1)-正则Cayley有向图。

2 定理证明

令Γ=Cay(G,S)是一个(X,1)-正则Cayley图,其中|S|=3,4,5,6,G

若|G:N|≥3,因为G作用在V(Γ)上正则,N作用在V(Γ)上半正则,考虑Γ关于N的正规商图ΓN,所以ΓN为G/N的Cayley图且G/N在X/N中无核。不失一般性,接下来我们设Γ=Cay(G,S)为d度无核Cayley有向图。考虑X作用在[X∶G]上的右乘作用以及X=GH,则X可视为Sn的子群,其中n=|X∶G|,显然,H在[X∶G]上作用正则,G为X在[X∶G]上作用的一个点稳定子群。一方面,由引理1,取一个元素x∈Sn(∪1≠T◁HNSn(T))且X=〈H,x〉,S={σ∈HxH|1σ=1},G=〈S〉,则Cos(X,H,x)≅Cay(G,S)≅Γ;另一方面,由引理2知Sn中所有同构的正则子群在Sn中共轭,所以在同构意义下Cos(X,H,x)与H的选择无关。注意到对任意的σ∈NSn(H),Cos(X,H,x)≅Cos (Xσ,H,xσ),于是利用此方法可以构造具有给定的点稳定子群H的(X,1)-正则Cayley图Cay(G,S)。本文主要研究有向图的情况,因此总是令S≠S-1,其中S-1={s-1|s∈S}。

①d=3。

若d=3,此时H≅Z3并且X≤S3。又Z3为S3的正规子群,因此不存在元素x∈S3(∪1≠T◁HNS3(T))使得Γ=Cos (X,H,x)。

②d=4。

③d=5。

假设Γ是一个5度(X,1)-正则Cayley图,其中G

④d=6。