一類Frobenius圖網(wǎng)絡

蔡曉霞,孔祥志,王 燕

(煙臺大學數(shù)學與信息科學學院,山東 煙臺 264005)

1 引言與預備知識

在近代圖論的發(fā)展中,隨著計算機網(wǎng)絡的誕生和發(fā)展,用圖來模擬網(wǎng)絡是研究和開發(fā)網(wǎng)絡的一個重要手段,凱萊圖因其天生的對稱性吸引了許多圖論學家的注意,在過去的幾十年中涌現(xiàn)出來許多好的凱萊圖網(wǎng)絡模型.

定義1[1]假設G是一個群,S?G且同時滿足以下條件:單位元e?S;對?a∈S,有a-1∈S;G=,則稱S是G的一個凱萊子集.

定義2[1]假設G是一個群,S是G的一個凱萊子集,構造凱萊圖Γ如下:Γ的頂點為G中所有的元素;對于任意的a,b∈G,a與b在Γ中有連邊當且僅當存在x∈S,有b=a·x,并記Γ=Cay(G,S).

定義3[2]設K和H為2個群,若φ為H到Aut(K)內(nèi)的同態(tài)映射,則稱φ為H在K上的一個作用.根據(jù)半直積理論,φ可以唯一確定一個K和H的半直積[K]H.特別地,如果H在K{1K}上的作用是半正則的(無不動點),就稱群G=[K]H為Frobenius群,稱K為這個群的Frobenius核,H為一個Frobenius補.

定義4[3]假設G是集合Ω上的一個置換群,則G在集合Ω×Ω上誘導了一個作用:任取(x,y)∈Ω×Ω,g∈G,都有(x,y)g=(xg,yg).如果G在Ω上作用是傳遞的,則把G在Ω×Ω上作用的軌道稱為軌道類(orbital). 此時集合{(x,x)|x∈Ω}為一個軌道類,稱為平凡軌道類;而集合(Ω)2={(x,y)|x,y∈Ω,x≠y}中包含的軌道類稱為非平凡的.

定義5[3]令G=[K]H是集合Ω上的一個Frobenius群. 一個圖Γ如果以Ω為頂點集,以集合E={{x,y}|(x,y)∈O}為邊集合,其中O為(Ω)2中包含的某個軌道類,就稱圖Γ為一個G-Frobenius圖. 如果G的Frobenius核是初等阿貝爾群,那么稱Frobenius圖Γ是仿射的.

文獻[3]中已經(jīng)證明一個G-Frobenius圖是它的核K的凱萊圖,相應的凱萊子集是H的一個軌道或者2個互逆軌道的并集.因此,Frobenius圖是弧傳遞(一個軌道時)或者邊傳遞且點傳遞(2個互逆軌道的并集時).

注1 (1)關于Frobenius圖的詳細定義和性質(zhì)請參考文獻[3].

(2)本文中提到的關于圖的相關定義可以參考文獻[1],關于群作用及其傳遞性的相關定義可以參考文獻[4].

2 一類特殊凱萊圖

考慮矩陣

顯然M∈GL(n,p)?Aut(K).M固定K的零元. 通過計算可知Mn=αI,因此M生成的子群H=〈M〉為εn階的循環(huán)群. 取e=(1,0,0,…,0)∈K,令集合S=eH≡{eMi|1≤i≤εn}.

注2如果令集合s={αt|0≤t≤ε-1},那么γ=Cay(Fp,s)就是一個度為ε的循環(huán)圖,并且Γ是γ的n次笛卡爾積.

下面討論Γ=Cay(K,S)的哈密爾頓性和連通性.

2.1 哈密爾頓性

定義6如果一個圖中的任意兩點都被一條哈密爾頓路(經(jīng)過圖中每個點一次且只一次的路)相連接就稱該圖為哈密爾頓連通的.

引理1[5]假設Γ是一個定義在阿貝爾群上的連通凱萊圖.如果val(Γ)=2,則Γ是一個圈;如果val(Γ)>2,那么只要Γ不是二部圖,Γ就是哈密爾頓連通的.

定理1 凱萊圖Γ=Cay(K,S)是哈密爾頓連通的.

證明根據(jù)定義2,Γ是阿貝爾群K上的連通凱萊圖.注意到γ=Cay(Fp,s)中有p-圈(0,α,2α,…,(p-1)α,0),因此γ不是一個二部圖,從而Γ不是一個二部圖. 于是由引理1知Γ是哈密爾頓連通的.

定義7 設Γ為一個度為2k的正則圖,如果Γ的邊集合E(Γ)可以分劃為k個哈密頓圈,則稱圖Γ為哈密爾頓可分解的.

引理2[6]如果Ci是一個圈,其中1≤i≤n,那么笛卡爾積Γ=C1×C2×…×Cn能夠分解為n個哈密爾頓圈.

定理2 上面構造的凱萊圖Γ=Cay(K,S)是哈密爾頓可分解的.

2.2 連通性

定義8 令Γ為一個連通圖,用δ(Γ)表示Γ中的最小的度.如果從Γ的邊(頂點)集中去掉一個i元子集之后變?yōu)橐粋€不連通圖或者平凡圖,那么就稱這個子集為i元的邊(點)割集;稱最小的邊(點)割集的元素個數(shù)為邊(點)連通度,記為λ(Γ)(κ(Γ)).

定義9 如果一個圖Γ滿足λ(Γ)=δ(Γ)(κ(Γ)=δ(Γ)),就稱圖Γ是最大邊(點)連通的.

定義10 如果Γ的所有最小邊(點)割集都是與一個點相關連的邊(點)構成的,那么稱Γ為超邊(點)連通圖.

引理3[7]令Cay(Zn,S)為一個循環(huán)圖,其中S={±a1,±a2,…,±ak}.如果當aj≥4時,(aj,n)=1,那么Cay(Zn,S)是最大點連通的.

定理3 上面構造的凱萊圖Γ=Cay(K,S)是最大點連通的.

證明根據(jù)定義,Γ是γ=Cay(Fp,s)的n次笛卡爾積.根據(jù)引理3可知γ是最大點連通的,再由引理4可知κ(Γ)≥nm=δ(Γ).根據(jù)Whitney不等式κ(Γ)≤δ(Γ),因此κ(Γ)=δ(Γ).

引理5[9]如果k≥2,那么Cay(Zn,{±1,±a2,…,±ak})是超邊連通圖.

由引理5容易得到γ=Cay(Fp,s)是超邊連通的.

引理6[10]給定2個正則且具有最大點連通度的圖G1和Γ,用遞歸的方法定義的圖Gn=Gn-1×Γ,n≥2,除了K2×Kn,n≥2之外都是超點和超邊連通的.

定理4 上面構造的凱萊圖Γ=Cay(K,S)是超點和超邊連通的.

證明注意到γ=Cay(Fp,s)滿足引理3是最大點連通的正則圖. 因為Γ是γ的n次笛卡爾積,滿足引理6的條件,因此Γ既是超點連通圖也是超邊連通圖.

3 Frobenius圖

下面證明凱萊圖Γ=Cay(K,S)在一定條件下還是Frobenius圖,這只需證明H在K{0}上作用半正則.

引理7矩陣M在K{0}上作用半正則.

證明令I為n階單位矩陣,則

假設存在x=(x1,x2,…,xn)∈K{0},但是x(I-M)=0,就可以得到下列方程組:

由假設知,存在k,1≤k≤n,xk≠0,根據(jù)方程組的前n-1個方程知x=(xk,…,xk),帶入方程組的最后一個方程可得:α=1,這與o(α)=ε為偶數(shù)階矛盾.

因此,任意的x=(x1,x2,…,xn)∈K{0},都有x(I-M)≠0,這說明1不是M的特征值,所以M在K上除零元外是無不動點的,即M在K{0}上作用半正則.

定理5如果pi|ε,i=1，…,r,那么H在K{0}上的作用是半正則的.

證明假設有y=(y1,…,yn)≠0使得Hy≠{e}.那么就存在正整數(shù)j|nε且j1.因為gcd(k,l)=1,l=ε,,所以gcd(ε,k)=1.

證明由定理5可知[K]H是一個Frobenius群,因此Γ是一個仿射的Frobenius圖.