论文部分内容阅读
图论的发展与著名的四色问题紧密相连。四色问题又称四色猜想：任何一张地图都可以用四种颜色使具有公共边界的国家染不同的颜色。Tutte在研究四色问题时引入了整数流概念。Tutte猜想：存在正整数k使得每个无桥图存在处处非零k-流。目前,这个猜想还未解决。由于Petersen图是无桥图并且不存在处处非零4-流,所以5是最好可能的。当k=5时也就是著名的5-流猜想。除去Petersen图,Tutte猜想：每个不含Petersen因子的无桥图存在处处非零4-流。他还进一步猜想：每个4-边连通图存在处处非零3-流。这就是Tutte的3-流、4-流和5-流猜想。1992年,Jaeger等人把整数流概念推广到群连通性上。群连通性不仅是整数流的推广,而且它有很好的性质：设A为k阶Abel群,H是图G的一个子图,如果H是A连通的并且G收缩H后有k-流,则图G存在处处非零k-流。令Zk表示k阶循环群。Jaeger等人还提出了两个与上述相对应的猜想：每个5-边连通图都是Z3-连通的,每个3-边连通图都是Z5-连通的。围绕这几个猜想,本文主要作了以下研究。首先,本文研究了顶点个数较小的3-边连通图。设G是阶数为n的3-边连通的简单图,A是一个阿贝尔群且|A|≥5。如果n≤15或者n=16且△≥4或者n=17且△≥5,则G是A-连通的。并且还得到了两个结论：若|E(G)|≥(n-15/2)+31,这里n≥17,则G是A-连通的；若IE(G)1≥(n-11/2)+23,这里n≥13。如果G*是通过不断收缩G的非平凡的A-连通子图直到不存在这样的图为止所得到的图,则称G可A-收缩到图G*。对此类图,我们证明了当|A|≥4时,则G是A-连通的或者G能被A-收缩到Petersen图。其次,本文研究了3-边连通图的群连通性和独立边数之间的关系。设A是-个阿贝尔群,|A|≥4。若G是一个3-边连通的简单图且其独立边数α’(G)≤5,则G是A-连通的或者G能被A-收缩到Petersen图。并且得到结论：若G满足上述条件,如果|A|≥5,则G是群A-连通的。最后,本文研究了局部连通图的群连通性。设G是3-边连通的,{H,K1,3}-free图。如果G是局部连通的,则G不是群Z3-连通的当且仅当G是图4-1中两个特殊图之一。