具有小度數(shù)的1-正則Cayley有向圖

居冉, 李玟, 李靖建

(廣西大學(xué) 數(shù)學(xué)與信息科學(xué)院, 廣西 南寧 530004)

1 引言及主要結(jié)果

本文中所有的圖都假定為有限簡(jiǎn)單連通圖。

設(shè)Γ是一個(gè)圖,圖Γ的頂點(diǎn)集、邊集、全自同構(gòu)群分別記為V(Γ)、E(Γ)、Aut(Γ)。設(shè)X≤Aut(Γ),若X在圖Γ的頂點(diǎn)集、邊集、弧集的作用是傳遞的,則稱圖Γ是X-點(diǎn)傳遞的、X-邊傳遞的、X-弧傳遞的,在此基礎(chǔ)上,若X=Aut(Γ),則稱圖Γ是點(diǎn)傳遞的、邊傳遞的、弧傳遞的。令s為正整數(shù),圖Γ中的一個(gè)s-弧是指Γ中(s+1)個(gè)頂點(diǎn)的序列(v0,v1,…,vs)滿足:當(dāng)0≤i≤s-1時(shí),vi和vi+1相鄰,且對(duì)任意1≤i≤s-1都有vi-1≠vi+1。如果Γ至少有一個(gè)s-弧,且X傳遞地作用在Γ的頂點(diǎn)集和s-弧集上,則稱圖Γ是(X,s)-弧傳遞的。如果X作用在其s-弧集上正則,則稱圖Γ是(X,s)-正則的。如果X=Aut(Γ),則稱圖Γ為s-正則的。設(shè)Γ是一個(gè)有向圖,v∈V(Γ)。本文稱以v為起點(diǎn)的有向邊的個(gè)數(shù)為v的出度,記作d+(v);而稱以v為終點(diǎn)的有向邊的個(gè)數(shù)為v的入度,記作d-(v)。本文中定義圖Γ的度數(shù)Val(Γ)=d+(v)。

設(shè)G是有限群,S是G的不含單位元的子集。群G關(guān)于子集S的Cayley圖定義為以群G中的元素為頂點(diǎn)和以{(a,b)|a,b∈G,ba-1∈S}為邊集的圖,記作Cay(G,S)。由定義可知,一個(gè)Cayley圖有度數(shù)|S|,Cay(G,S)連通當(dāng)且僅當(dāng)G=〈S〉。本文稱Cayley圖是正規(guī)的,如果G在Aut(Cay(G,S))中正規(guī)。對(duì)于非正規(guī)Cayley圖Γ,若存在Aut(Γ)的一個(gè)正規(guī)子群N,其作用在頂點(diǎn)集合V(Γ)上半正則且恰好有2條軌道,則稱圖Γ是雙正規(guī)的。令CoreX(G)∶=∩x∈XGx,對(duì)于G≤X≤Aut(Γ),若CoreX(G)=1,則稱Cayley圖Cay(G,S)無(wú)核。

設(shè)G是有限群,S是G的(可以包含單位元的)子集。群G關(guān)于子集S的Bi-Cayley圖定義為以G×{0,1} 為頂點(diǎn)集和以{{(g,0),(sg,1)}|g∈G,s∈S}為邊集的圖,記作BCay(G,S)。

定理1設(shè)Γ=Cay(G,S) 是一個(gè)d度(X,1)-正則Cayley有向圖,d=3,4,5,6。設(shè)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是一個(gè)有向圈,要么ΓN是例1至例3中的一個(gè),特別地,當(dāng)Val(Γ)=Val(ΓN)時(shí),在同構(gòu)意義下,Γ是例2、3中的圖。

1 預(yù)備知識(shí)

設(shè)X為有限群,H為X的一個(gè)無(wú)核子群,X右乘作用在集合[X∶H]∶={Hx|x∈X}上忠實(shí)。定義陪集圖Γ=Cos(X,H,HgH),其頂點(diǎn)集為[X∶H],邊集為{(Hx,Hdx)|d∈HgH}。由定義容易得出,如果〈H,g〉=X,則Γ連通。令α=H,β=Hg,則點(diǎn)穩(wěn)定子群Xα=H,Xβ=Hg,弧穩(wěn)定子群Xαβ=Xα∩Xβ=H∩Hg。

令Γ是一個(gè)X-點(diǎn)傳遞圖,N是X的正規(guī)子群,VN表示N作用在V(Γ)上的軌道集合。定義由N誘導(dǎo)的Γ的正規(guī)商圖ΓN其頂點(diǎn)集為VN,若存在a∈A且b∈B在原圖中相鄰,則兩頂點(diǎn)A,B∈VN在ΓN中相鄰。用Val(Γ)表示Γ的度,如果Val(Γ)=Val(ΓN),則稱Γ為ΓN的正規(guī)覆蓋?？紤]XA=NXα,其中A∈V(ΓN),α∈A,因此(X/N)A?XA/N?Xα。本文有如下性質(zhì):

性質(zhì)1(X/N)A?XA/N?Xα,其中A∈V(ΓN),α∈A。

關(guān)于弧傳遞圖,本文有如下引理:

引理1[12]令Γ=Cay(G,S)為連通(X,1)-正則Cayley有向圖,其中G

引理2[13]Sn的任意2個(gè)同構(gòu)的正則子群在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。通過計(jì)算得H?Z6,|H:H∩Hxi|=6,此時(shí)Γi是一個(gè)Xi-弧傳遞6度圖。令Si={σ∈HxiH|1σ=1},Gi=〈Si〉。計(jì)算可得:

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是一個(gè)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。通過計(jì)算得H?S3,|H:H∩Hxi|=6,此時(shí)Γi是一個(gè)Xi-弧傳遞6度圖。令Si={σ∈HxiH|1σ=1},Gi=〈Si〉。計(jì)算可得:

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是一個(gè)6度(Xi,1)-正則Cayley有向圖。

2 定理證明

令Γ=Cay(G,S)是一個(gè)(X,1)-正則Cayley圖,其中|S|=3,4,5,6,G

若|G:N|≥3,因?yàn)镚作用在V(Γ)上正則,N作用在V(Γ)上半正則,考慮Γ關(guān)于N的正規(guī)商圖ΓN,所以ΓN為G/N的Cayley圖且G/N在X/N中無(wú)核。不失一般性,接下來(lái)我們?cè)O(shè)Γ=Cay(G,S)為d度無(wú)核Cayley有向圖?？紤]X作用在[X∶G]上的右乘作用以及X=GH,則X可視為Sn的子群,其中n=|X∶G|,顯然,H在[X∶G]上作用正則,G為X在[X∶G]上作用的一個(gè)點(diǎn)穩(wěn)定子群。一方面,由引理1,取一個(gè)元素x∈Sn(∪1≠T?HNSn(T))且X=〈H,x〉,S={σ∈HxH|1σ=1},G=〈S〉,則Cos(X,H,x)?Cay(G,S)?Γ;另一方面,由引理2知Sn中所有同構(gòu)的正則子群在Sn中共軛,所以在同構(gòu)意義下Cos(X,H,x)與H的選擇無(wú)關(guān)。注意到對(duì)任意的σ∈NSn(H),Cos(X,H,x)?Cos (Xσ,H,xσ),于是利用此方法可以構(gòu)造具有給定的點(diǎn)穩(wěn)定子群H的(X,1)-正則Cayley圖Cay(G,S)。本文主要研究有向圖的情況,因此總是令S≠S-1,其中S-1={s-1|s∈S}。

①d=3。

若d=3,此時(shí)H?Z3并且X≤S3。又Z3為S3的正規(guī)子群,因此不存在元素x∈S3(∪1≠T?HNS3(T))使得Γ=Cos (X,H,x)。

②d=4。

③d=5。

假設(shè)Γ是一個(gè)5度(X,1)-正則Cayley圖,其中G

④d=6。