徐尚進(jìn)

(廣西大學(xué),廣西 南寧 530004)

1 引言

圖是比較容易被人們直觀理解并也容易激發(fā)人們產(chǎn)生豐富想像的對(duì)象.而圖論研究的圖,通常是經(jīng)過抽象以后僅剩下一些頂點(diǎn)和連接這些頂點(diǎn)的邊的幾何圖形.本文所涉及的圖則更為特殊,即有限簡(jiǎn)單無(wú)向圖,其頂點(diǎn)個(gè)數(shù)有限且無(wú)自環(huán),邊不重且無(wú)向,并還具有某些對(duì)稱性.由于圖的這些對(duì)稱性需要通過其全自同構(gòu)群的某些傳遞性來(lái)描述,因此需要運(yùn)用群及其作用的理論.這方面工作屬于群與圖研究領(lǐng)域,我們稱之為“傳遞圖”研究.

我們先回顧代數(shù)結(jié)構(gòu)的自同構(gòu)群.

設(shè)Ω∶={α1,α2,…,αn}是一個(gè)有限集,則Ω到自身的雙射(也稱為“置換”)的全體關(guān)于映射的乘法構(gòu)成一個(gè)n！階有限群, 稱為n次對(duì)稱群, 記作Sym(Ω).

進(jìn)一步,若Ω不是一個(gè)普通集合,而是一個(gè)代數(shù)結(jié)構(gòu),比如Ω是一個(gè)偏序集,或者是一個(gè)群、一個(gè)環(huán),則我們通常會(huì)重點(diǎn)考慮Sym(Ω)中保持Ω的代數(shù)結(jié)構(gòu)關(guān)系的置換σ：

(1) 當(dāng)Ω是偏序集時(shí),σ要能保持Ω的序,即由αiαj有其中表示αi在σ作用下的象(下同);

(3) 當(dāng)Ω是一個(gè)環(huán)時(shí),σ要能同時(shí)保持Ω的加法和乘法, 即

Sym(Ω)中能保持上述代數(shù)結(jié)構(gòu)關(guān)系的置換稱為Ω的自同構(gòu).容易驗(yàn)證,Ω的全體自同構(gòu)組成一個(gè)群,稱為Ω的自同構(gòu)群,記作Aut(Ω).顯然有

1 ≤Aut(Ω) ≤Sym(Ω).

由于自同構(gòu)觸及Ω的代數(shù)結(jié)構(gòu),因此研究Aut(Ω)及其作用對(duì)于了解Ω本身結(jié)構(gòu)是有效的.

有限簡(jiǎn)單圖作為由有限的頂點(diǎn)集和有限的邊集決定的組合結(jié)構(gòu),也同樣可以定義它的自同構(gòu)群,并通過自同構(gòu)群來(lái)研究圖本身的性質(zhì),特別是圖的對(duì)稱性.為了方便陳述,我們先給出有限簡(jiǎn)單無(wú)向圖及其全自同構(gòu)群等有關(guān)概念.

定義1.1有限簡(jiǎn)單無(wú)向圖Γ的頂點(diǎn)集記作V(Γ),|V(Γ)|稱為Γ的階.以頂點(diǎn)v,u∈V(Γ)為端點(diǎn)的(無(wú)向)邊記作{v,u},邊集記作E(Γ).與v∈V(Γ)連邊的頂點(diǎn)全體稱為v的鄰域,記作N(v),|N(v)|稱為v的度數(shù),記作deg(v).如果Γ的一個(gè)由兩兩不同頂點(diǎn)組成的序列v0,v1,…,vl滿足{vi-1,vi}∈E(Γ)(i=1,2,…,l),則這個(gè)頂點(diǎn)序列稱為Γ的一條l-路,記作[v0,v1,…,vl],其中l(wèi)稱為這條路的長(zhǎng).特別地,長(zhǎng)大于2且首尾相等的l-路[v0,v1,…,vl-1,vl=v0]稱為l-圈,記作Cl.如果圖Γ的任意兩頂點(diǎn)之間至少存在一條路相連,則稱Γ是連通的.

定義1.2有限簡(jiǎn)單無(wú)向圖Γ的一個(gè)自同構(gòu)是指頂點(diǎn)集V(Γ)上保邊的一個(gè)置換σ∈Sym(V(Γ)),它滿足:{u,v}∈E(Γ)當(dāng)且僅當(dāng){u,v}σ∶={uσ,vσ}∈E(Γ).圖Γ的自同構(gòu)全體關(guān)于置換的乘法構(gòu)成Sym(V(Γ))的一個(gè)子群,稱為圖Γ的全自同構(gòu)群,記作Aut(Γ).

如圖1,Aut(Γ1)=1,Aut(Γ2)=Sym({v1,v2,v3,v4})≌S4.

圖1

考慮圖Γ的全自同構(gòu)群Aut(Γ)在其頂點(diǎn)集V(Γ)上的作用(本文記作Aut(Γ)↘V(Γ)).如果兩個(gè)頂點(diǎn)v,u∈V(Γ)同屬于一個(gè)軌道,即存在一個(gè)圖自同構(gòu)σ∈Aut(Γ)使vσ=u,則v與u明顯具有相同的度數(shù),即deg(v)=deg(u).如果Aut(Γ)↘V(Γ)傳遞,即對(duì)V(Γ)中任意兩點(diǎn)v,u都存在一個(gè)圖自同構(gòu)σ∈Aut(Γ)使vσ=u,則稱Γ是點(diǎn)傳遞圖.這時(shí)Γ是正則圖(即所有頂點(diǎn)度數(shù)相等).由于圖自同構(gòu)保持邊不變,而邊與邊以及邊與點(diǎn)之間的鄰接情況又決定了圖的結(jié)構(gòu),即圖論性質(zhì),因此點(diǎn)傳遞圖每個(gè)頂點(diǎn)的圖論性質(zhì)都一樣, 這就是圖的對(duì)稱性.Aut(Γ)在頂點(diǎn)集V(Γ)上的作用也可以誘導(dǎo)在邊集E(Γ)上的作用,即{v,u}σ∶={vσ,uσ}.如果這個(gè)作用是傳遞的, 則稱Γ是邊傳遞圖.同樣, 邊傳遞圖每條邊的圖論性質(zhì)都一樣, 所以也具有一定的對(duì)稱性.

值得一提的是,圖的點(diǎn)傳遞性與邊傳遞性之間并沒有聯(lián)系.如圖2,Aut(Γ3)=〈(123)(456),(12)(45),(14)(25)(36)〉,Γ3是點(diǎn)傳遞但不是邊傳遞圖,因?yàn)樗倪厈v1,v2}是某個(gè)3-圈的邊,但邊{v1,v4}不是,所以邊{v1,v2}不能傳到邊{v1,v4};Γ4是完全二部圖K3,4,Aut(Γ4)=〈(1234),(12),(567),(56)〉.Γ4邊傳遞但不點(diǎn)傳遞, 因?yàn)樗徽齽t.

圖2

利用有限群很容易構(gòu)造點(diǎn)傳遞圖，比如本文用到的Cayley圖.

定義1.3[1]設(shè)G是有限群,S是G#∶=G{1}的一個(gè)自逆子集(即S-1=S)，則以G為頂點(diǎn)集,以{{g,sg}|g∈G,s∈S}為邊集定義的圖稱為G關(guān)于S的Cayley圖,記作Cay(G,S).

性質(zhì)1.4[2]設(shè)Γ∶=Cay(G,S)是群G關(guān)于其子集S的Cayley圖.分別記A∶=Aut(Γ),A1是A關(guān)于G的單位元1的點(diǎn)穩(wěn)定子,Aut(G,S)∶={α∈Aut(G)|Sα=S}，則

(1)G的單位元1的鄰域N(1)=S;

(2)G的右正則表示R(G) ≤A,因此Γ是點(diǎn)傳遞圖,因而是|S|-度正則圖，并且A=R(G)A1,R(G)∩A1=1;

(3) Aut(G,S)=Aut(G)∩A≤A1，進(jìn)而Aut(G,S)正規(guī)化R(G);

(4)Γ連通當(dāng)且僅當(dāng)G=〈S〉.

V(Qk)∶=V(k,2),E(Qk)∶={{v,εi+v}|v∈V(k,2),εi∈S}.

由于S-1=S且〈S〉=V(k,2),因此Qk是2k階k-度連通無(wú)向圖.圖3中的兩個(gè)圖分別是2-,3-立方圖.

圖3

比點(diǎn)傳遞和邊傳遞條件更強(qiáng)的是弧傳遞條件.

定義1.6每條無(wú)向邊{v,u}可看作是由一對(duì)方向相反的有向邊(v,u)與(u,v)組成,因此無(wú)向圖Γ的邊集也可看作是由一對(duì)對(duì)方向相反的有向邊組成.這時(shí)的有向邊又稱為弧,弧集記作Arc(Γ).如果Aut(Γ)誘導(dǎo)作用在弧集Arc(Γ)上傳遞,則稱Γ是弧傳遞圖.

根據(jù)定義,弧傳遞圖明顯是點(diǎn)傳遞和邊傳遞的,但反之不然.例如圖2的點(diǎn)傳遞圖Γ3和邊傳遞圖Γ4都不是弧傳遞的.

顯然(v,u)σ=(v′,u′).由于置換σ把Ω的不相交的(k-1)-元子集仍變?yōu)椴幌嘟坏?k-1)-元子集,因此σ保邊,即σ∈Aut(Ok),從而Ok是弧傳遞的.

圖4是2-,3-度奇圖O2和O3.

圖4

需要提醒讀者的是,k-立方圖Qk和k-度奇圖Ok都是有限傳遞圖中較具代表性的.

接下來(lái)引入本文用到的偶圈(圈長(zhǎng)為偶數(shù))對(duì)邊集的概念.

定義1.8設(shè)Γ是無(wú)向圖,l=2k≥4是偶數(shù).如果經(jīng)過邊{v0,v1}∈E(Γ)存在一個(gè)l-圈[v0,v1,…,vk-1,vk,vk+1,…,vl-1,vl=v1](見圖5),則稱邊{vk,vk+1}是邊{v0,v1}的l-圈對(duì)邊.

圖5

如果E(Γ)的一個(gè)包含邊{v,u}的子集當(dāng)且僅當(dāng)包含邊{v′,u′}時(shí)包含{v′,u′}的l-圈對(duì)邊,則稱該子集為邊{v,u}的l-圈對(duì)邊集,記作El(v,u).

注:(1) 若經(jīng)過邊{v,u}無(wú)l-圈,則El(v,u)={{v,u}};(2) {v′,u′}∈El(v,u)?El(v′,u′)=El(v,u).

例1.9觀察可知,圖2中Γ3的4-圈對(duì)邊集共有4個(gè),分別是E4(v1,v2)={{v1,v2},{v4,v5}},E4(v1,v3)={{v1,v3},{v4,v6}},E4(v2,v3)={{v2,v3},{v5,v6}}和E4(v1,v4)={{v1,v4},{v3,v6},{v2,v5}};而圖Γ4的6-圈對(duì)邊集只有1個(gè),即E6(v1,v5)=E(Γ4).

例1.10試決定k≥ 2-立方圖Qk的4-圈對(duì)邊集.

解任取{v,u}∈E(Qk).沿用例1.5的記號(hào),則u=v+εi,其中εi∈S.然而經(jīng)過邊{v,u}的4-圈只能是[v,u,u+εj,v+εj,v],其中εj∈S,j≠i.說明邊{v+εj,u+εj}是邊{v,u}的4-圈對(duì)邊,即{v+εj,u+εj}∈E4(v,u).根據(jù)偶圈對(duì)邊集的定義,當(dāng)邊{v′,u′}∈E4(v,u)時(shí),有?ε∈S,邊{v′+ε,u′+ε}∈E4(v,u).再由V(k,2)是S生成的加群,即知E4(v,u)={{v+w,u+w}|w∈V(k,2)}.

例1.11試決定k≥3-度奇圖Ok的6-圈對(duì)邊集.

解先證Ok連通,即證Ok的任意兩頂點(diǎn)v與u之間存在一條路.為此,對(duì)|v∩u|=i0.取v′∶={1,2，…,k-1},u′∶={k+1,k+2,…,2k-1}∈V(Ok)，則{v,u′},{v′,u′}∈E(Ok)，再由|v′∩u|=i-1及歸納假設(shè)得,v′與u之間存在一條路, 因此v與u之間也存在一條路.即Ok是連通圖.

然后決定Ok的6-圈對(duì)邊集.任取{v,u}∈E(Ok).根據(jù)奇圖的構(gòu)造知,存在唯一的i∈Ω(v+u).由此可定義E(Ok)到Ω的映射f,使f(v,u)=i.顯然,f(v,u)=f(v,u).以下證明Ok具有下述的一些性質(zhì),也決定其邊的6-圈對(duì)邊集.

(1) 若[v0,v1,v2]是2-路,則v0∪v2?Ωv1且f(v0,v1)≠f(v1,v2).

圖6

圖7

事實(shí)上, 由v0≠v2及Ω=v0+v1+{f(v0,v1)}=v1+v2+{f(v1,v2)},即知結(jié)論成立.

(2)Ok沒有3-圈.

事實(shí)上,由(1)知任意2-路[v0,v1,v2]首尾的并集v0∪v2Ωv1，因此|v0∪v2|≤k.利用公式|v0|+|v2|=|v0∪v2|+|v0∩v2|及|v0|=|v2|=k-1,推出2k-2≤k+|v0∩v2|，因此|v0∩v2|≥k-2>0,即{v0,v2}?E(Ok),說明Ok沒有3-圈.

(3) 設(shè)[v0,v1,v2,v3]是Ok的一條3-路，則f(v1,v2)∈v0∩v3.

事實(shí)上,由(1),f(v1,v2)≠f(v2,v3)以及f(v1,v2)∈Ω(v1+v2)Ωv2=v3+{f(v2,v3)},即得f(v1,v2)∈v3.同理,f(v1,v2)=f(v2,v1)∈v0.(3)得證.

(4)Ok沒有4-圈.

事實(shí)上,由(3)知任一條3-路[v0,v1,v2,v3]的首尾v0,v3有交,即{v0,v3}?E(Ok),導(dǎo)致Ok沒有4-圈.

(5)Ok存在5-圈當(dāng)且僅當(dāng)k=3.

v0Ωv1v2+{f(v1,v2)},v4Ωv3v2+{f(v2,v3)}.

再由v0∩v4=?及f(v1,v2) ≠f(v2,v3),推出v0+v4v2+{f(v1,v2)}+{f(v2,v3)}.比較兩邊的階,得2k-2=|v0+v4|≤|v2|+2=k+1，因此k≤3,但只能有k=3.

(5)得證.

(6) 經(jīng)過任一條3-路[v0,v1,v2,v3]有且僅有一個(gè)6-圈,并且圈上的每對(duì)對(duì)邊都取相同的f值.

先證存在性.由v1∩v2=?及(3)有，f(v2,v3)∈v1,f(v0,v1)∈v2，從而f(v2,v3)≠f(v0,v1).于是可取與v3連邊的頂點(diǎn)v4=Ω(v3+ {f(v0,v1)})∈V(Ok).而由f(v1,v2)∈v3=v3v4,又可取與v4連邊的頂點(diǎn)v5=Ω(v4+{f(v1,v2)})∈V(Ok).這時(shí),

f(v0,v1)=Ω(v3+v4)=f(v3,v4),f(v1,v2)=Ω(v4+v5)=f(v4,v5).

(1.1)

由于Ok無(wú)3-,4-圈,因此[v0,v1,v2,v3,v4,v5]是一條5-路(見圖8).

圖8

往證v0∩v5=?且v0∪v5=v2∪v3.事實(shí)上,由Ω=v0+v1+{f(v0,v1)}=v1+v2+{f(v1,v2)}，有v0+{f(v0,v1)}=v2+{f(v1,v2)},由此得

v0={f(v1,v2)}+v2{f(v0,v1)}.

(1.2)

而由Ω=v4+v5+{f(v4,v5)}=v3+v4+{f(v3,v4)}有v5+{f(v4,v5)}=v3+{f(v3,v4)},又得

v5={f(v3,v4)}+v3{f(v4,v5)}={f(v0,v1)}+v3{f(v1,v2)}.

(1.3)

由于f(v1,v2)≠f(v0,v1)及v2∩v3=?,故從(1.2)與(1.3)二式可推出v0∩v5=?且v0∪v5=v2∪v3.

至此,得{v0,v5}∈E(Ok),即[v0,v1,v2,v3,v4,v5,v0]是6-圈,并經(jīng)過3-路[v0,v1,v2,v3](見圖9).

圖9

再由(1.1)及f(v0,v5)=Ω(v0∪v5)=Ω(v2∪v3)=f(v2,v3),知圈上的每對(duì)對(duì)邊都取相同的f值.

圖10

(7) 邊{v,u}∈E(Ok)的6-圈對(duì)邊集E6(v,u)={{v′,u′}|f(v′,u′)=f(v,u)}.

由(6)及Ok的連通性即可證(7)成立.

偶圈對(duì)邊集明顯具有圖論性質(zhì), 它在研究圖的對(duì)稱性時(shí)可發(fā)揮關(guān)鍵作用. 本文利用偶圈對(duì)邊集的圖論性質(zhì)證明了具有6-圈的某些二面體群Cayley圖的正規(guī)性. 偶圈對(duì)邊集的概念也很新穎, 涉及的是圖的傳遞性問題, 運(yùn)用的是抽象群的理論.

本文引入的概念和記號(hào)大都是通用的, 對(duì)于未定義而引用的概念和記號(hào), 讀者可查閱文獻(xiàn)[2,3].

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

先介紹一些本文用到的概念、性質(zhì)和結(jié)論.

性質(zhì)2.2[2]Γ正規(guī)當(dāng)且僅當(dāng)A1=Aut(G,S).

引理2.3[2]設(shè)?！?Cay(G,S)是有限群G的Cayley圖.若|Aut(Γ)1|≤2,則Γ是正規(guī)Cayley圖.

引理2.4[4]設(shè)Γ∶=Cay(G,S)是連通3-度非弧傳遞Cayley圖,則Γ正規(guī)當(dāng)且僅當(dāng)Aut(Γ)1誘導(dǎo)作用在S上忠實(shí).

引理2.5[5]設(shè)Γ∶=Cay(G,S)是有限交換群G的連通Cayley圖.若S的任意兩個(gè)非互逆二元子集{s1,s2}與{s3,s4}在s1s2=s3s4時(shí)相等,則Γ是正規(guī)Cayley圖.

定義2.6在Cayley圖Cay(G,S)中,由s1,s2,…,sl∈S組成的序列(s1,s2,…,sl)稱為G的S-序列.如果s1,s2,…,sl∈S可生成以某頂點(diǎn)g∈G為起點(diǎn)的l-路(圈)[g,s1g,s2s1g,…,sl…s2s1g],則稱(s1,s2,…,sl)為G的對(duì)應(yīng)于該路(圈)的強(qiáng)S-序列.

由定義2.6易知

性質(zhì)2.7S-序列(s1,s2,…,sl)是強(qiáng)S-序列的充要條件是，?l≥j>i≥1,j-i

例2.8設(shè)Γ∶=Cay(G,S).若S中含有l(wèi)>2階元s,則Γ存在l-圈Cl.

證明顯然,[1,s,s2,…,sl-1,sl=1]是Γ的l-圈Cl.而(s,s,…,s)(l個(gè)分量)是對(duì)應(yīng)于該圈的強(qiáng)S-序列.

引理2.9設(shè)?！?Cay(G,S).若s≠s′∈S可交換但不互逆,則Γ存在4-圈.

證明由s′s=ss′即知[1,s,s′s,s′,1]是Γ的4-圈.而(s,s′,s-1,s′-1)是對(duì)應(yīng)于該圈的強(qiáng)S-序列.

引理2.10[2]圖?；鬟f的充要條件是Γ點(diǎn)傳遞且A∶=Aut(Γ)關(guān)于v∈V(Γ)的點(diǎn)穩(wěn)定子群Av誘導(dǎo)作用在N(v)上傳遞.

定義2.11設(shè)Γ是簡(jiǎn)單圖,K≤Aut(Γ).子集△V(Γ)稱為K的不變區(qū)或K-不變區(qū),如果△K△.對(duì)于只含一個(gè)元素的不變區(qū),該元素稱為不動(dòng)點(diǎn).特別地,當(dāng)K=〈α〉時(shí),〈α〉-不變區(qū)簡(jiǎn)稱α-不變區(qū),〈α〉-不動(dòng)點(diǎn)則簡(jiǎn)稱α-不動(dòng)點(diǎn).

引理2.12[6]設(shè)?！?Cay(G,S)是群G的Cayley圖,s∈S是A∶=Aut(Γ)關(guān)于1的點(diǎn)穩(wěn)定子A1的不動(dòng)點(diǎn)，則

(1) ?α∈A,g∈G,sgα=(sg)α,(g,sg)α=(gα,sgα);

(2)A≤Aut(Cay(G,S{s}));

(3) ?v∈V(Γ),svSv=N(v)是Av-不動(dòng)點(diǎn).特別地,當(dāng)v∈N(1)=S時(shí),sv是A1作用在N(1)上的核的不動(dòng)點(diǎn).

證明(1) 易知R(g)αR[(gα)-1]∈A1,因此s=sR(g)αR[(gα)-1]=(sg)α(gα)-1，于是sgα=(sg)α.進(jìn)而(g,sg)α=(gα, (sg)α)=(gα,sgα).

(2) 設(shè)α∈A,s′∈S{s}，則由(1)知,(gα,sgα)=(g,sg)α≠(g,s′g)α=(gα,s″gα),由這推出s″∈S{s},即得α∈Aut(Cay(G,S{s})).

(3) ?α∈Av,由(1)即得(sv)α=svα=sv.

引理2.13[2]若Cayley圖?！?Cay(G,S)連通,則|Aut(Γ)1|沒有大于|S|的素因子.

證明用反證法.若有素?cái)?shù)p>|S|且p||A1|,則A1含p階元α.由于素?cái)?shù)階循環(huán)群〈α〉↘N(1)的軌道長(zhǎng)只能是1或p,但不能是p(否則與|N(1)|=|S|

由引理2.13顯然有

推論2.14記號(hào)及條件同引理2.13,并設(shè)△是含于S的階最大的Aut(Γ)1-不變區(qū),則|Aut(Γ)1|沒有大于|△|的素因子.

推論2.15[6]3-度或4-度連通Cayley圖Γ的點(diǎn)穩(wěn)定子Aut(Γ)1是{2,3}-群.

3 主要結(jié)論

定理3.1設(shè)G是有限交換群,S=S-1G#(不必生成G),s∈S,則Cayley圖?！?Cay(G,S)滿足:

(1) 經(jīng)過邊{1,s}至少有|S{s±1}|個(gè)4-圈;

(2)S的任意兩個(gè)非互逆二元子集{s1,s2}與{s3,s4}在s1s2=s3s4時(shí)相等，則經(jīng)過邊{1,s}只有|S{s±1}|個(gè)4-圈;

(3) 經(jīng)過邊{1,s}只有│S{s±1}│個(gè)4-圈，則|E4(1,s)|=│〈S{s±1}〉│.

證明(1) 任取s′∈S{s±1},則(s,s′,s-1,s′-1)是一組強(qiáng)S-序列,并生成經(jīng)過邊{1,s}的一個(gè)4-圈[1,s,s′s,s′,1](見圖11).因此經(jīng)過邊{1,s}至少有│S{s±1}│個(gè)4-圈.

圖11

圖12

(3) 由(1)及題設(shè)可知,經(jīng)過邊{1,s}的4-圈只能由s和s′∈S{s±1}做成的強(qiáng)S-序列(s,s′,s-1,s′-1)生成.這時(shí),邊{s′,ss′}={1,s}R(s′)恰是邊{1,s}的一條4-圈對(duì)邊,即{1,s}R(s′)∈E4(1,s)(見圖13).任取s″∈S{s±1},則(s,s″,s-1,s″-1)也是一組強(qiáng)S-序列,它可生成由s′出發(fā)并經(jīng)過邊{s′,ss′}的一個(gè)4-圈[s′,ss′,s″ss′,s″s′,s′](見圖13).這時(shí),邊{s″s′,s″ss′}={s′s″,ss′s″}={s′,ss′}R(s″)恰是邊{s′,ss′}的4-圈對(duì)邊,因此也有{s′,ss′}R(s″)={1,s}R(s′s″)∈E4(1,s),并且s′s″∈〈S{s±1}〉.

圖13

由此可知E4(1,s)中的邊形如{v,sv},其中v∈〈S{s±1}〉.往證,當(dāng)E4(1,s)包含邊{v,sv}時(shí),對(duì)于任意s′∈S{s±1},邊{v,sv}R(s′)恰是邊{v,sv}的4-圈對(duì)邊.事實(shí)上,利用強(qiáng)S-序列(s,s′,s-1,s′-1)可生成經(jīng)過邊{v,sv}的一個(gè)4-圈[v,sv,s′sv,s′v,v](見圖13).而邊{s′v,s′sv}={vs′,svs′}={v,sv}R(s′)正是邊{v,sv}的一條4-圈對(duì)邊,因此{(lán)v,sv}R(s′)∈E4(1,s).

上述事實(shí)等價(jià)于E4(1,s)={{1,s}R(g)|g∈〈S{s±1}〉},即證明了(3).

例3.2k-立方圖Qk滿足定理3.1的條件,因此是正規(guī)Cayley圖,并且經(jīng)過每條邊都恰有k-1個(gè)4-圈.

證明沿用例1.5的記號(hào)并利用其結(jié)論,則k-立方圖Qk是Cayley圖Cay(G,S),其中G是加群V(k,2),S={ε1,ε2,…,εk}.若S的任意兩個(gè)非互反二元子集{εi1,εi2}和{εi3,εi4}滿足εi1+εi2=εi3+εi4,則εi3+εi4只有第i1和第i2這兩個(gè)分量是1,其余分量是0,由此推出{εi1,εi2}={εi3,εi4}.即Qk滿足定理3.1的條件.再由Qk的點(diǎn)傳遞性及引理2.5,即知Qk是正規(guī)Cayley圖.這時(shí),經(jīng)過Qk的每條邊都恰有|S|-1=k-1個(gè)4-圈.比如,經(jīng)過Q2的每條邊都恰有1個(gè)4-圈,經(jīng)過Q3的每條邊都恰有2個(gè)4-圈.

定理3.3取2n階二面體群G∶=〈a,b|an=b2=1,b-1ab=a-1〉的4-元自逆子集S∶={ai,a-i,ajb,b},其中j≠±i,±2i,n/2，則4-度Cayley無(wú)向圖?！?Cay(G,S)滿足:

(1) 經(jīng)過邊{1,b}和邊{1,ajb}各有2個(gè)4-圈,并且|E4(1,b)|=|E4(1,ajb)|=o(ai);

(2) 經(jīng)過邊{1,ai}和邊{1,a-i}各有2個(gè)4-圈,并且|E4(1,ai)|=|E4(1,a-i)|=2o(aj).特別地,當(dāng)o(ai)≠2o(aj)時(shí),{ai,a-1}和{ajb,b}都是Aut(Γ)1-不變區(qū);

證明(1) 取兩組強(qiáng)S-序列(b,ai,b,ai)和(b,a-i,b,a-i),即可構(gòu)造經(jīng)過邊{1,b}的2個(gè)4-圈[1,b,aib,a-i,1]和[1,b,a-ib,ai,1].同理,經(jīng)過邊{1,ajb}也有2個(gè)4-圈[1,ajb,aj+ib,a-i,1]和[1,b,aj-ib,ai,1].由此,過頂點(diǎn)1恰有4個(gè)4-圈,并可組成一個(gè)“田”字.再由Cayley圖的點(diǎn)傳遞性,可得Γ的一個(gè)局部如圖14(距離超過4的頂點(diǎn)可能重復(fù), 但不影響證明).

容易看出,導(dǎo)出子圖[〈ai〉∪b〈ai〉]同構(gòu)于梯圖Co(ai)×K2,而邊{1,b}的4-圈對(duì)邊集E4(1,b)中的邊恰是該梯圖的所有“階梯”,因此E4(1,b)={{1,b}R(g)|g∈〈ai〉}.同理,E4(1,ajb)={{1,ajb}R(g)|g∈〈ai〉}.從而|E4(1,b)|=|E4(1,ajb)|=o(ai).

(2) 由圖14即知經(jīng)過邊{1,ai}和邊{1,a-i}也各有2個(gè)4-圈.此外,圖自同構(gòu)R(a-ib)把邊{1,ai}變到其4-圈對(duì)邊{1,ai}R(a-ib)={b,a-ib};而圖自同構(gòu)R(aj)把邊{1,ai}變到{b,a-ib}的4-圈對(duì)邊{1,ai}R(aj)={aj,aj+i}.因此,{1,ai}R(a-ib),{1,ai}R(aj)∈E4(1,ai).進(jìn)一步,圖自同構(gòu)R(a-j-ib)把邊{1,ai}變到{aj,aj+i}的4-圈對(duì)邊{1,ai}R(a-j-ib)={a-jb,a-j-ib};而圖自同構(gòu)R(a2j)把邊{1,ai}變到{a-jb,a-j-ib}的4-圈對(duì)邊{1,ai}R(a2j)={a2j,a2j+i}.因此,{1,ai}R(a-j-ib),{1,ai}R(a2j)∈E4(1,ai).如此繼續(xù)下去,可推出E4(1,ai)={{1,ai}R(g)|g∈〈aj〉∪〈aj〉a-ib}.同理,E4(1,a-i)={{1,a-i}R(g)|g∈〈aj〉∪〈aj〉aib}.從而,|E4(1,ai)|=|E4(1,a-i)|=2o(aj).事實(shí)上,E4(1,ai)和E4(1,a-i)中的邊也分別是兩個(gè)都同構(gòu)于C2o(aj )×K2的梯圖的“階梯”.

由于偶圈對(duì)邊集的階是圖論性質(zhì), 故當(dāng)o(ai)≠2o(aj)時(shí),Aut(Γ)1顯然不能在{ai,a-1}與{ajb,b}之間互變頂點(diǎn), 由此{(lán)ai,a-1}和{ajb,b}都是Aut(Γ)1-不變區(qū).

圖14

(4) 由題設(shè),易知〈S〉=〈aib,ajb〉=G,并且o(ai)≠2o(aj).再由(3)和(2),即知A1是作用在N(1)上忠實(shí)的2-群,并且{ai,a-1}和{ajb,b}都是A1-不變區(qū).進(jìn)而由推論2.14,A1只含對(duì)合,因此是階整除4的初等交換2-群.

(3.1)

先證β是良定義的,即當(dāng)g∈btakj〈ai〉∩btak′j〈ai〉(t∈{0, 1})時(shí), 根據(jù)映射關(guān)系(3.1),理應(yīng)有

gβ=btg-1bta2kj=btg-1bta2k′j.

(3.2)

事實(shí)上,由g=btakj+li=btak′j+l′i，有(k-k′)j≡(l′-l)i(modn)，于是i|k-k′，故2(k-k′)j≡0(modn),說明(3.2)成立,即β是良定義的.其次證β是A1中異于α的對(duì)合.已有1β=1，再由(akj+li)β2=(akj-li)β=akj+li，(bakj+li)β2=(bakj-li)β=bakj+li，即知β是對(duì)合.

再證β保邊,即?g∈G,s∈S={ai,a-i,ajb,b},往證(gβ,(sg)β)=(gβ,s′gβ),s′∈S,或證(sg)β(gβ)-1∈S.以下分4種情況證明.

情況1s=ai

若g=akj+li∈akj〈ai〉,則sg=akj+li+i,(sg)β(gβ)-1=(akj+li+i)β[(akj+li)β]-1=akj-li-i(akj-li)-1=a-i∈S.

若g=bakj+li∈bakj〈ai〉,則sg=bakj+li-i,(sg)β(gβ)-1=(bakj+li-i)β[(bakj+li)β]-1=bakj-li+i(bakj-li)-1=bakj-li+i(a-kj+lib)=ai∈S.

情況2s=a-i

證明類似情況1,略.

情況3s=ajb

若g=akj+li∈akj〈ai〉,則

sg=ba(k-1)j+li∈ba(k-1)j〈ai〉,

(sg)β(gβ)-1=(ba(k-1)j+li)β[(akj+li)β]-1=ba(k-1)j-li(akj-li)-1=ajb∈S.

若g=bakj+li∈bakj〈ai〉,則

sg=a(k+1)j+li,

(sg)β(gβ)-1=(a(k+1)j+li)β[(bakj+li)β]-1=a(k+1)j-li(bakj-li)-1=a(k+1)j-li(a-kj+lib)=ajb∈S.

情況4s=b

若g=akj+li∈akj〈ai〉,則

sg=bakj+li∈bakj〈ai〉,(sg)β(gβ)-1=(bakj+li)β[(akj+li)β]-1=bakj-li(akj-li)-1=b∈S.

若g=bakj+li∈bakj〈ai〉,則

sg=akj+li∈akj〈ai〉,

(sg)β(gβ)-1=(akj+li)β[(bakj+li)β]-1=akj-li(bakj-li)-1=akj-li(a-kj+lib)=b∈S.

至此證明了β是A1中對(duì)合.再由β不動(dòng)頂點(diǎn)b,可得β≠α.進(jìn)而A1=〈α,β〉=2×2,即|A1|=4.只需證,假設(shè)2ij?0(modn),則A1=〈α〉.任取則σ只能是對(duì)合.以下分兩種情況討論.

情況1σ不動(dòng)b

情況2bσ=ajb

特別地,當(dāng)2ij?0(modn)時(shí),由上述證明知|A1|=2.再由引理2.3,即知Γ是正規(guī)Cayley圖.

定理3.4設(shè)二面體群G∶=〈a,b|an=b2=1,ab=a-1〉,S是G的元素不少于3個(gè)且都形如aib的子集(不必生成G).記?！?Cay(G,S),A∶=Aut(Γ),k=|S|-1,并取s∈S，則

(1)Γ=[〈a〉,〈a〉b]是二部圖,即Γ的每條邊都有且僅有一個(gè)端點(diǎn)含于〈a〉;

(4) 當(dāng)S={aib,ab,b},3

(5) 當(dāng)n=2ip,i≥2,p是奇素?cái)?shù),S={apb,a2jb,a2j(2p2-1)b,b},1≤j≤i時(shí),Γ是正規(guī)Cayley圖,并且|A1|=2.

證明(1) 顯然(證略).

圖15

(3) 由(2)及題設(shè)可知,經(jīng)過邊{1,s}的6-圈就只能由s和s′≠s″∈S{s}做成的強(qiáng)S-序列(s,s′,s″,s,s′,s″)生成.這時(shí),邊{s′s″,ss′s″}={1,s}R(s′s″)恰是邊{1,s}的一條6-圈對(duì)邊,即{1,s}R(s′s″)∈E6(1,s).并且{1,s}的6-圈對(duì)邊形如{v,sv},其中v∈〈a〉(見圖15).

往證,當(dāng)E6(1,s)包含邊{v,sv}(v∈〈a〉)時(shí),?s′≠s″∈S{s},邊{v,sv}R(s′s″)恰是邊{v,sv}的6-圈對(duì)邊,并且vR(s′s″)∈〈a〉.事實(shí)上,利用強(qiáng)S-序列(s,s′,s″,s,s′,s″)可生成經(jīng)過邊{v,sv}的一個(gè)6-圈(見圖16).

圖16

由于v,s′s″∈〈a〉,因此邊{v,sv}R(s′s″)={v(s′s″),sv(s′s″)}={s′s″v,ss′s″v}正是邊{v,sv}的一條6-圈對(duì)邊,進(jìn)而{v,sv}R(s′s″)∈E6(1,s).至于vR(s′s″)=v(s′s″)∈〈a〉則是顯然的.

上述事實(shí)等價(jià)于E6(1,s)={{1,s}R(g)|g∈〈(S{s})2〉},即證明了(3).

(4) 這時(shí),a≠ai-1≠a1-i≠a-1,a-1b≠a2-ib,ai-1b≠a2b,ai≠a-i.易知Γ關(guān)于頂點(diǎn)1的3 -步鄰域如圖17.

圖17

情況1當(dāng)j≥i-1時(shí),由S的生成關(guān)系可得1的2-步鄰域如圖18.

圖18

由于A1在N(1)中已有兩個(gè)不動(dòng)點(diǎn),因此|A∶R(G)|=|A1|≤2,因而Γ正規(guī).再由α∈Aut(G,S)≤A1，得|A1|=2.

情況2當(dāng)i≥3且j≤i-2時(shí),由S的生成關(guān)系可得1的2-步鄰域如圖19.

圖19

[1,b,a2j,a2j+1(p2-1)b,a2j+1(1-p2),a2j(2p2-1)b,1],

[1,b,a2j(2p2-1),ap-2j(2p2-1)b,a2j(2p2-1)-p,apb,1],

由A1在N(1)中存在2個(gè)不動(dòng)點(diǎn)apb和b,立得|A∶R(G)|=|A1|≤2.再由引理2.3,即知Γ正規(guī).又由α∈Aut(G,S)≤A1，可得|A1|=2.