李良辰，張小霞，張會芹

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

0 前言

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

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

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

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

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

設整數k大于等于1.如果實值函數

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

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

則稱函數f是圖Γ上的一個k-流.定義

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

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

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

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

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

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

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

1 預備知識及引理

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

設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所有橫檔構成的集合記作ER(Ln).

引理1[2]一個3-正則圖存在處處非零3-流當且僅當它是二部圖.

引理2 如果圖Γ可以分解成邊不交的子圖并且這些子圖是圈或3-正則二部圖，那么圖Γ存在處處非零3-流.

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

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

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

證明對于群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′.不妨設gτ=gat，從而τ=at.又因為

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

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

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

2 主要結論

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

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

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

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

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

因為

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

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

若S包含3個對合，即

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

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

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

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

ER(Q3)=ER(Γ1).

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

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

3 結束語

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