張曉輝，溫 玉，郝 英

(邯鄲學(xué)院 數(shù)理學(xué)院，河北 邯鄲 056002)

?

完全多部圖同構(gòu)于一類循環(huán)群的Cayley齊次分解

張曉輝，溫 玉，郝 英

(邯鄲學(xué)院 數(shù)理學(xué)院，河北 邯鄲 056002)

設(shè)Γ=Ks[t]是一個(gè)完全多部圖，R=Zn=〈a〉是一個(gè)循環(huán)群，其中n=st。令Τ=〈as〉?Zt、S=RT，那么Γ=Ks[t]?Cay(R,S)。構(gòu)造出了多部圖Γ同構(gòu)于循環(huán)群的一類齊次分解，并對這種齊次分解進(jìn)行了刻畫。

完全多部圖； 循環(huán)群； 齊次分解

定義1 設(shè)G是一個(gè)群，S為G的非空真子集，我們稱如下定義的圖為群G關(guān)于S的Cayley圖：VΓ=G，且頂點(diǎn)u和v是連接的充要條件為uv-1∈S。這個(gè)Cayley圖記為：Cay(G,S)。

定義2[1]設(shè)Γ是一個(gè)圖，AΓ是圖Γ的弧集。設(shè)= {P1,P2,…,Pk}(k≥2)是AΓ的一個(gè)分類，那么我們可以誘導(dǎo)出圖Γ的一些子圖Γi=(VΓ,Pi)。我們稱Γi為圖Γ的因子，而稱Γ=Γ1+Γ2+…+Γk為圖Γ的一個(gè)分解。當(dāng)Γi兩兩同構(gòu)時(shí)我們稱該分解為圖Γ的同構(gòu)分解。

設(shè)Γ=Γ1+Γ2+…+Γk是圖Γ的一個(gè)同構(gòu)分解。由于Γi=(VΓ,Pi)兩兩同構(gòu)，所以Γi=

定義3[2]假設(shè)={P1,P2,…,Pk}是弧集AΓ的一個(gè)分解(k≥2)，M

(i)M在頂點(diǎn)集VΓ上是傳遞的，并且M穩(wěn)定每個(gè)集合Pi。

定義4 如果M在頂點(diǎn)VΓ上是正則的，并且M?G，這時(shí)稱定義2中的齊次分解為M-Cayley齊次分解。此時(shí)，由誘導(dǎo)的子圖Γi叫做M-Cayley圖。

定義5 由單個(gè)的n階元素a生成的群稱為循環(huán)群，記作Zn=〈a〉。

引理2 設(shè)群G傳遞作用于非空集合Ω上，H?G且H在Ω上不傳遞，則H在Ω上半傳遞。

引理3[3]設(shè)Γ=Cay(R,S)是一個(gè)Cayley圖，H是Aut(R,S)的一個(gè)子群且H在S上半傳遞，則圖Γ存在一個(gè)各因子度數(shù)均相等的分解。

任取Pi∈。由于(yg)(xg)-1= yx-1∈Si，我們有。又因?yàn)镠保持Si不變，所以，即保持每個(gè)Pi不變。

任取Pi∈，則yx-1∈Si。因?yàn)長在傳遞，所以存在Si∈，使得(yg)l((xg)l)-1=(ygg-1x-1)l=(yx-1)l∈Sj，由已知在VΓ上傳遞，進(jìn)而。又因?yàn)?，所以，即保?{P1,P2,…,Pk}不變。

任取Pi,Pj∈、(x,y)∈Pi，則yx-1∈Si。因?yàn)長在上傳遞，故存在g∈L，使得yg(xg)-1=(yx-1)g∈Sj，進(jìn)而(x,y)g=(xg,yg)∈Pj。又因?yàn)?，所以，即L在上傳遞。進(jìn)一步，由于，我們有G也在傳遞。

引理5 設(shè)R=〈a〉是一個(gè)循環(huán)群，其中 ° (a)=n=st。令T=〈as〉、S=RT，則Aut(R,S)=Aut(R,T)=Aut(R)。

證明 ?σ∈Aut(R,S)，則Sσ=S，即(RT)σ=RT，進(jìn)而Tσ=T。所以我們有

=Aut(R,T)

該引理的前半部分得證。

所以我們有〈as〉=〈ais〉=〈(as)δ〉=〈as〉δ，即Tδ=T，進(jìn)而Aut(R)?Aut(R,T)。又因?yàn)锳ut(R,T)?AutR，所以Aut(R,T)=AutR。證畢。

現(xiàn)在我們按照引理4提供的方法來構(gòu)造圖Γ=Ks[t]?Cay(R,S)(R為循環(huán)群)的齊次分解，并對具備這種齊次分解的圖進(jìn)行刻畫。對此我們有下面的定理成立。

定理1 圖Γ=Ks[t]?Cay(R,S) (R為循環(huán)群)具有引理4所提供的齊次分解，當(dāng)且僅當(dāng)s=t,t=pe，其中p是一個(gè)素?cái)?shù)。

反之，設(shè)Γ=Kp[pe]是一個(gè)完全多部圖，其中p是一個(gè)素?cái)?shù)。令R=Zpe+1=〈b〉、T=〈bp〉?Zpe、S=RT，那么Γ=Kp[pe]?Cay(R,S)。顯然b∈S，又因?yàn)?/p>

所以：

[1] GIUDICI M,LI C H,POTOCNIK P,et al.Homogeneous factorisations of graph products[J].Discrete Math,2008,308:3652-3667.

[2] 張曉輝，盧建岳，李根亮，等.完全圖的循環(huán)齊次分解[J].云南大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,32(3):254-257.

[3] LI C H,GIUDICI M,PRAEGER C E.Homogeneous factorizations of complete graphs with edge-transitive factors[J].Algebraic Combin,2009,29:107-132.

[4] LI C H,PRAEGER C E.Homogeneous factorisations of complete multipartite graphs[J].Discrete Math,2007,307:415-431.

[5]LI C H.On isomorphisms of finite Cayley graphs-asurvey[J].Discrete Mathematics,2002,256:301-334.

[6] 徐明曜.有限群導(dǎo)引(上,下冊)[M].北京：科學(xué)出版社,1999.

[7] 張遠(yuǎn)達(dá).有限群構(gòu)造[M].北京：科學(xué)出版社,1982.

Cayley homogeneous factorization of complete multipartite graphs isomorphic to cyclic group

ZHANG Xiaohui,WEN Yu,HAO Ying

(Department of Mathematics,Handan College,Handan, Hebei 056002,China)

Let Γ=Ks[t]be a complete multipartite graphs, R=Zn=〈a〉 is a cyclic group, n=st. Let Τ=〈as〉?Zt、S=RT, that Γ=Ks[t]?Cay(R,S).we can characterize a class of homogeneous factorization of the complete multipartite graphs Γisomorphism to cyclic group.

complete multipartite graphs;cyclic group;homogeneous factorization

1004—5570(2016)06-0050-02

2016-06-20

河北省社科基金(201603040127)

張曉輝(1982-)，女，河北人，講師，研究方向：群與圖方面，E-mail: nizi112@126.com.

O175

A