顾粉霞, 蒋梓炜, 卢春霞, 梁 栋, 朱 佳, 杨 帆

(江苏科技大学 数理学院， 江苏 镇江 212003)

图的邻域并及度条件与Z3-连通性

顾粉霞, 蒋梓炜, 卢春霞, 梁 栋, 朱 佳, 杨 帆

(江苏科技大学 数理学院， 江苏 镇江 212003)

邻域并条件;Z3-连通性;处处非零3-流

令G是一个图,给定G的方向D.若一条边e=uv∈D(G)是由点u指向点v,则称u是边e的尾,v是边e的头.对于一个点v∈V(G),定义E+(v)是以点v为尾的边的集合,E-(v)是以点v为头的边的集合.令A是一个非平凡的阿贝尔群,A*=A-{0}.定义F(G,A)={f|f:E(G)→A},F*(G,A)={f|f:E(G)→A*}.

当∂f=0时，f∈F(G,A)是一个A-流.当f∈F*(G,A)且∂f=0时,f是一个处处非零的A-流.若f是一个处处非零的Z-流且对于所有e∈E(G),|f(e)|

文献[2-3]中介绍了整数流问题.文献[4]中推广了处处非零流并引入群连通性概念.下面的猜想是由Jaeger等人提出的,到现在为止仍然没有得到证明.

猜想1[4]任意5-边连通图是Z3-连通图.

国内外学者围绕着这个猜想做了很多的工作.最近度条件被用来证明图中处处非零3-流及Z3-连通性的存在性.一些结果可以在参考文献[5-11]中看到.令G是n阶图.若对于任意一对不相邻的点u,v,d(u)+d(v)≥n，则称图G满足Ore-条件.文献[8]中列举出了所有满足Ore-条件的Z3-连通图且得到了下面的定理.

定理1[8]若G(n≥3)是一个简单图,满足Ore-条件,那么图G要么是Z3-连通图,要么是图1的12个图中的一个.

图1 满足Ore-条件的非Z3-连通图Fig.1 Graphs satisfying Ore-condition but is not Z3-connected

图的Z3-连通性与哈密尔顿性质有着密切的联系.文献[12] 在证明哈密尔顿圈的存在性时首次引入了邻域并条件.受此启发,文献[13]中考虑了图的邻域条件与Z3-连通性,并证明了如下结果.

在定理2的基础上,降低邻域并条件,得到了如下定理.

1 引……

登录APP查看全文