廣義雙循環(huán)群上Cayley圖中的處處非零3-流

李良辰，張小霞，張會(huì)芹

(1．洛陽師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院，河南 洛陽 471934;2．信陽師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 信陽 464000)

0 前言

文中除特別說明外，圖都是簡單無向的有限圖.未作說明的概念和符號參見文獻(xiàn)[1].

設(shè)A是具有一個(gè)2階元y的交換群.廣義雙循環(huán)群G=Dic(A,x)是由群A和元素x生成，且滿足

[G:A]=2,x2=y,

并且對任意的a∈A有x-1ax=a-1.

設(shè)D(Γ)是圖Γ的一個(gè)定向,記E(Γ)為圖Γ的定向邊的集合.如果E(G)中的邊e=uv的方向是從頂點(diǎn)u指向v,則稱u為e的起點(diǎn),v為e的終點(diǎn).對V(G)中的任意頂點(diǎn)v,定義

設(shè)整數(shù)k大于等于1.如果實(shí)值函數(shù)

f:E(Γ)→{0,±1,±2,±(k-1)},

對于任意的v∈V(Γ),有

則稱函數(shù)f是圖Γ上的一個(gè)k-流.定義

S(f)={e∈E(Γ):f(e)≠0}.

如果S(f)=E(Γ),則稱k-流f為處處非零k-流.整理流理論是Tutte[2,3]研究四色問題時(shí)引入的，并提出了著名的3-流猜想.

猜想1 每個(gè)4-邊連通圖存在處處非零3-流.

Jaeger[4]證明了每個(gè)4-邊連通圖存在處處非零k-流.圖中處處非零3-流是否存在引起了眾多學(xué)者的研究興趣.2012年，THOMASSEN[5]做出重要突破，證明了每個(gè)8-邊連通圖存在處處非零3-流.隨后,Lovász等[6]改進(jìn)這個(gè)結(jié)果,證明了每個(gè)6-邊連通圖存在處處非零3-流.盡管如此,猜想1仍然沒有解決.

設(shè)G是單位元為1的有限群,S是G-{1}的子集并且S=S-1.我們構(gòu)造一個(gè)圖Γ=Cay(G,S),Γ的頂點(diǎn)集合V(Γ)=G,而邊集合E(Γ)={gh：g,h∈G且g-1h∈S},稱為群G關(guān)于S的Cayley圖.

圖Γ到自身的同構(gòu)映射稱為自同構(gòu).圖Γ的全體自同構(gòu)在置換乘法之下構(gòu)成一個(gè)群，稱為Γ的全自同構(gòu)群，記為Aut(Γ).顯然1≤Aut(Γ)≤Sym(Γ).如果Aut(Γ)在頂點(diǎn)集V(Γ)上傳遞,則稱Γ為點(diǎn)傳遞圖.容易證明,每個(gè)度為k的點(diǎn)傳遞圖都是k-邊連通的[7].因此,如果猜想1成立,那么度不小于4的點(diǎn)傳遞圖存在處處非零3-流.

在所有的點(diǎn)傳遞圖中,我們了解最深刻的莫過于Cayley圖.POTOCNICK等[8]證明了交換群上的度不小于4的Cayley圖存在處處非零3-流.對非交換群，ALSPACH等[9]證明了每個(gè)度不小于2的可解群上的Cayley圖存在處處非零4-流.YANG等[10]驗(yàn)證3-流猜想對于定義在二面體群上的Cayley圖是成立的.文獻(xiàn)[11]推廣了他們的結(jié)果.受此啟發(fā)，我們主要研究定義在廣義雙循環(huán)群上的Cayley圖中處處非零3-流的存在性.

1 預(yù)備知識(shí)及引理

一個(gè)連通的2-正則圖稱為圈.設(shè)n為大于等于2的正整數(shù)，含有n個(gè)頂點(diǎn)的圈記為Cn,含有n個(gè)頂點(diǎn)的路記為Pn.設(shè)有兩個(gè)圖Γ1和Γ2.圖Γ1和Γ2的笛卡爾積Γ1□Γ2是以V(Γ1)×V(Γ2)為頂點(diǎn)集的圖，其中Γ1□Γ2的兩個(gè)頂點(diǎn)(u1,v1)和(u2,v2)相鄰當(dāng)且僅當(dāng)u1=u2,v1v2∈E(Γ2)或u1u1∈E(Γ1)，v1=v2.

設(shè)V(Pn)={1,2,…,n}，V(K2)={1,2}.在圖Pn□K2中添加邊(1,1)(n,1)和(n,2)(1,1)的圖稱為循環(huán)梯，記作CLn.若在圖Pn□K2中添加邊(1,1)(n,2)和(1,1)(n,1)，則所得之圖為莫比烏斯梯，記作MLn.這兩種圖統(tǒng)稱為閉梯，記作Ln.對于1≤i≤n，邊(i,1)(i,2)稱為閉梯Ln的橫檔.閉梯Ln所有橫檔構(gòu)成的集合記作ER(Ln).

引理1[2]一個(gè)3-正則圖存在處處非零3-流當(dāng)且僅當(dāng)它是二部圖.

引理2 如果圖?？梢苑纸獬蛇叢唤坏淖訄D并且這些子圖是圈或3-正則二部圖，那么圖Γ存在處處非零3-流.

E(Fi)∩E(Fj)=ER(Fi)∩ER(Fj),i≠j.

(4)不料孩子突然死亡,婦人又慷慨自殺,——我心將要怎樣呢,而且她為什么死?老友,你知道么?她為愛我和你底妹妹而出此的。

引理4 設(shè)τ∈A是廣義二面體群G的一個(gè)對合，a是G的一個(gè)階大于等于3的元素，則Cay(G,{a,a-1,τ})是閉梯的并，并且其中的橫檔是由τ生成.

證明對于群G中任意的元素g,考慮下面兩個(gè)圈

C:g,ga,ga2,…gas-1,gas=g,

C′:gτ,gτa,gτa2,…gτas-1,gτas=gτ,

其中s=orda.如果gτ∈V(C)，則C=C′.不妨設(shè)gτ=gat，從而τ=at.又因?yàn)?/p>

τ2=(at)2=1,orda=s.

如果gτ?V(C)，則C和C′是不同的圈.如果a∈A，那么gai通過τ-邊與gaiτ=gτai相鄰，其中i=0,1,…,s-1.否則，設(shè)a=αtx，這里αi∈A,則有

gaτ=gαtxτ=gτa.

2 主要結(jié)論

定理1 若廣義雙循環(huán)群G=Dic(A,x)上定義的Cayley圖Cay(G,S)的度不小于4,則Cay(G,S)存在處處非零3-流.

證明設(shè)Γ=Cay(G,S)是定義在廣義雙循環(huán)群G=Dic(A,x)上的度大于等于4的Cayley圖.注意到，Γ是|S|-正則圖.因?yàn)槎葹榕紨?shù)的點(diǎn)傳遞圖存在處處非零3流，故可設(shè)|S|是奇數(shù).

群G中由兩個(gè)對合生成的圖或由一個(gè)階不小于3的元素生成的圖記為H.顯然，H是圖Γ的2-因子，所以圖H存在處處非零3-流.從而，只需證明圖G-H存在處處非零3-流.對|S|歸納可知，只需證|S|=5時(shí)定理成立即可.因?yàn)殡A數(shù)大于2的元素是在S成對出現(xiàn)的，故S中含有奇數(shù)個(gè)對合.

由廣義雙循環(huán)群的定義可知，

Dic(A,x)={axi|i=0,1,a∈A}.

因?yàn)?/p>

(ax)2=ax·ax=aa-1xx=x2=y≠1，

所以廣義雙循環(huán)群的對合必包含于群A中.由于S的生成集，S中不可能含有5個(gè)對合.

若S包含3個(gè)對合，即

S={τ1,τ2,τ3,a,a-1}，

其中τ1,τ2,τ3∈A;a,a-1∈G-A.容易驗(yàn)證由τ1,τ2,τ3-邊生成的圖同構(gòu)于Q3.由引理4，

Γ1=Cay(G,{a,a-1,τ1})

是一個(gè)閉梯.顯然，Γ=Q3∪Γ1,并且

ER(Q3)=ER(Γ1).

由引理3知，此時(shí)圖Γ中存在處處非零3-流.

若S={τ,b,b-1a,a-1}，其中τ∈A.根據(jù)引理4可得，Cayley圖Cay(G,{a,a-1,τ})和Cay(G,{a,a-1,τ})都是以τ-邊為其橫檔的閉梯的并.由引理3知，此時(shí)圖Γ中存在處處非零3-流.證畢.

3 結(jié)束語

本文驗(yàn)證了定義在廣義雙循環(huán)群上的Cayley圖中處處非零3-流的存在性，即Tutte的3-流猜想對這類圖是成立的.這個(gè)結(jié)果為研究圖中處處非零3-流的存在性提供了幫助.