论文部分内容阅读
整数流理论是被Tutte作为解决四色猜想的工具引入的，设D是图G的一个定向，E+D(v)(D-D(v))表示以v为起点(终点)的所有边的集合，如果存在映射f：E(G)→{±1，±2，...，±(k-1)}使得对任意v∈V(G)有那么称G存在处处非零k-流.Tutte猜想：每个4-边连通图存在处处非零3-流。1992年，Jaeger等在文献[10]中把整数流的概念推广为群连通的概念，设A是单位元为0的Abel加群.如果对任意b：V(G)→A并且满足∑v∈V(G)b(v)=0，存在映射f：E(G)→A-{0}使得对任意v∈V(G)有则称G是A-连通的，令Z3表示3阶循环群.Jaeger等在文献[10]中猜想：每个5-边连通图都是Z3-连通的.围绕这两个猜想，本文主要作了以下研究。
首先，本文研究了最小度满足一定条件的简单二部图.设G是阶数为n的简单二部图，在本文中，我们证明了：若δ(G)≥[n/4]+1，则除一个特殊图以外，G存在处处非零3-流.并且还证明了：若n≥13且δ(G)≥[n/4]+1，则G是Z3-连通的。这里我们要特别指出，两个结论中最小度的下界是最好可能的。
其次，本文研究了不相邻两点的邻域并满足一定条件的2-边连通图.设G是阶数n≥14的2-边连通图.如果G*是通过不断收缩G的非平凡的Z3-连通子图直到不存在这样的图为止所得到的图，则称G可Z3-收缩为G*.对此类图，我们证明了：若对任意uv()E(G)有|N(u)∪N(i)|≥[2n/3]，则G不是Z3-连通的当且仅当G可Z3-收缩为{G3，K4，K￣4，L}之一，其中L是由完全图K4加上一个与其两个点相邻的顶点得到的图。
再次，本文研究了广义二面体群和广义四元数群上的Caylcy图，并且证明了3-流猜想对这两类群上的Cayley图是成立的.本文的这个结果也推广了Yang和Li在[Information Processing Letters，111(2011)416-419]中的结论。
最后，本文研究了定义在Abcl群上的点传递图，并且证明了度不小于4的Abel群上的点传递图存在处处非零3-流.我们的这个结果推广了Potocnik，Skoviera和Skrekovski在[Discrete Mathematics，297(2005)，119-127]中的结果。