论文部分内容阅读
整数流理论是被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]中的结果。