Abel群上点传递图中的处处非零3-流

李良辰， 秦春艳

(洛阳师范学院 数学科学学院 河南 洛阳 471022)



Abel群上点传递图中的处处非零3-流

李良辰， 秦春艳

(洛阳师范学院 数学科学学院 河南 洛阳 471022)

Tutte猜想每个4-边连通图存在处处非零3-流. 验证3-流猜想对于定义在Abel群上的点传递图是成立的,这个结果推广了Potocnik等在2005年的研究结果.

点传递图； Abel群； 处处非零3-流

0 引言

文中除特别说明外，图都是简单无向的有限图. 未作说明的概念和符号参见文[1-2].

设D(G)表示图G的某个定向. 如果E(G)中的边e=uv的方向是从顶点u指向v,则称u为e的起点,v为e的终点. 对V(G)中的任意顶点v,定义

其中“∑”表示在群A中的加法.

猜想1[4]每个4-边连通图存在处处非零3-流.

图G到自身的同构映射称为自同构. 图G的全体自同构在置换乘法之下构成一个群，称为G的全自同构群，记为Aut(G). 显然1≤Aut(G)≤Sym(G). 如果Aut(G)在顶点集V(G)上传递,则称G为点传递图.

Tutte最早提出整数流理论,并且提出猜想1. Jaeger[5-6]证明了每个4-边连通图存在处处非零4-流. 从文献[7]可以知道,度为k的点传递图是k-边连通的. 因此,若3-流猜想成立,则度不小于4的点传递图存在处处非零3-流.

在所有的点传递图中,我们了解最深刻的莫过于Cayley图. 最近,Alspach等[8]证明了每个度不小于2的可解群上的Cayley图存在处处非零4-流.

Potacnik,Skoviera和Skrekovski证明了3-流猜想对Abel群上的Cayley图是成立的.

定理1 每个度不小于4的Abel群上的Cayley图存在处处非零3-流[1].

定理2 若Γ上的点传递图G(Γ,K,S)的度不小于4,则G(Γ,K,S)存在处处非零3-流.

1 引理

设映射f∈V(G)→V(G′)是满射并且保持顶点之间的相邻关系. 如果对任意u∈V(G),f把G中与u关联的边一一映射到G′中与f(u)关联的所有边,则称f是G到G′的覆盖映射. 图G称为图G′的覆盖图. 若G′存在处处非零k-流φ,则由φ可以得到G的处处非零k-流ψ(只需要令ψ(e)=φ(f(e)),其中e∈E(G)). 归纳可得下面的引理1[9].

引理1 设f:G→G′是覆盖映射. 若G′存在处处非零3-流,则G存在处处非零3-流.

2 定理2的证明

当K=1时,G(Γ,K,S)=G(Γ,1,S)=G(Γ,S). 由定理1得,G(Γ,K,S)存在处处非零3-流.

当K≠1时,因为K是Γ的子群,所以K是Γ的正规子群. 取N=K. 从而,S∩KN=S∩K=Φ.

进而可得

G(Γ,K,S)=G(Γ/K,K/K,S/K)=G(Γ/K,1,S/K)=G(Γ/K,S/K),

并且G是Cayley图G(Γ/K,S/K)的覆盖图.

因为Γ是Abel群,所以Γ/K也是Abel群. 由定理1得,G(Γ/K,S/K)存在处处非零3-流. 由引理2得,G(Γ,K,S)存在处处非零3-流. 定理得证.

[1]PotocnikP,SkovieraM,SkrekovskiR.Nowhere-zero3-flowsinabelianCayleygraphs[J].DiscreteMath, 2005,297 (1/2/3): 119-127.

[2]BondyJA,MurtyUSR.GraphsTheroywithApplications[M].NewYork:MacmillanPress,1976.

[3]TutteWT.Onthealgebraictheoryofgraphcolorings[J].JCombinTheory, 1966,1 (1): 15-50.

[4]TutteWT.Acontributiononthetheoryofchromaticpolynomial[J].CanadJMath, 1954,6 (1): 80-91.

[5]JaegerF.Onnowhere-zeroflowsinmultigraphs[C]//ProceedingsoftheFifthBritishCombinatorialConference,Cong.NumerantiumXV,UtilitasMathWinnipeg,1976.

[6]JaegerF.Flowsandgeneralizedcoloringtheoremsingraphs[J].JCombinTheorySerB, 1979,26 (2): 205-216.

[7]WatkinsAE.Connectivityoftransitivegraphs[J].JCombinTheory, 1970, 8 (1): 23-29.

[8]AlspachB,LiuY,ZhangCQ.Nowhere-zero4-flowsandCayleygraphsonsolvablegroups[J].SIAMJDiscreteMath, 1996,9 (1): 151-154.

[9]NanasiovaM,SkovieraM.Nowhere-zeroflowsinCayleygraphsandSylow2-subgroups[J].JAlgCombin, 2009,30 (1): 103-110.

(责任编辑：王浩毅)

Nowhere-zero 3-Flows in Vertex Transitive Graphs on Abelian Group

LI Liang-chen， QIN Chun-yan

(DepartmentofMathematics,LuoyangNormalUniversity,Luoyang471022,China)

It was conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow by Tutte. This conjecture was verified for vertex transitive graphs on abelian group,which generalized the result of the research by Potocnik in 2005.

vertex transitive graph; abelian group; nowhere-zero 3-flow

2015-02-12

国家自然科学基金资助项目，编号11301254；河南省高等学校重点科研项目，编号13A110800；洛阳师范学院青年基金资助项目，编号2012-QNJJ-003．

李良辰(1982-)，男，河南安阳人，副教授，博士，主要从事整数流问题研究，E-mail:liangchen_li@163.com.

李良辰，秦春艳. Abel群上点传递图中的处处非零3-流[J].郑州大学学报：理学版，2015，47(3)：34-36.

O157.5

A

1671-6841(2015)03-0034-03

10.3969/j.issn.1671-6841.2015.03.006