连通图群连通性的度条件

摘要

本文考虑的图均为有限图,但是图中可能包含重边,对于图G=G(V,E),我们用V(G)和E(G)表示图的顶点集合与边集合.对于图G中的不相交顶点子集V1,V2,定义e(V1,V2)为端点分别在V1,V2中的边的集合.特别的,当V1=X,且V2=V(G)-X时,用(δ)(X)代替e(X,V(G)-X).
　　 定义图G上的方向D=D(G),若边e∈E(G)的方向为由点u到点v,则我们称tail(e)=u与head(e)=v.并且对于图G中的一个顶点v∈V(G),定义
　　 E-D(v)={e∈E(D):v=tail(e)}与E+D(v)={e∈E(D):v=head(e)}.
　　 A是非平凡的阿贝尔加法群,0是它的加法单位元,记A*=A-0表示A中非零元素的集合,并定义函数
　　 F(G,A)={f:E(G)→A}与F*(G,A)={f:E(G)→A*}.
　　 给定函数f∈F(G,A),定义(δ)f:V(G)→A如下:
　　 (δ)f(v)=∑e∈E+D(v)f(e)-∑e∈E-D(v)f(e)
　　 对于图G,如果∑6(b)=0,则称函数b:V(G)→A为A零值加和函数.这种函数的集合用Z(G,A)表示.给定b∈Z(G,A),若存在函数f∈F*(G,A)使得(δ)f=b,则称f为(A,b)-处处无零流.若对于任意b∈Z(G,A),图G都存在(A,b)-处处无零流,则称图G为A连通的.
　　 作为解决图的染色问题的重要工具,处处无零流理论由Tutte在十九世纪五十年代提出.经过半个世纪的研究与发展,其理论日益成熟和完善,并被推广与扩展到群连通理论.群连通理论作为处处无零流理论的延伸,不仅是解决一系列理论问题的重要方法与工具,同时在通信网络设计、计算机科学等中都有非常重要的应用.群连通理论研究的重心主要是在确定一般图的群连通度上.
　　 本文主要讨论了满足一定度条件的一般图的群连通度问题.全文共分三章,第一章简单介绍了图论的基本概念,群连通理论的历史与发展状况以及一些已有的相关结论.
　　 第二章讨论了满足一定度条件的图的群连通度,证明了以下结论:
　　 定理2.1.1 A为满足|A|≥4的阿贝尔群,图G为简单二边连通图,并且满足n=|V(G)|≥21.如果对于任意u,v∈V(G)且uv(∈)E(G)都有maxd{d(u),d(v)}≥≥n/5,则图GA-连通图,或者G*∈图集P.进一步,若有G*∈{K2,5,K2,4,K2,3,C4},则有∧g(G)=5;若有G*=C5,则∧g(G)=6;若有G*=C6,则∧g(G)=7.
　　 在第三章中我们还提出了一些问题,以待进一步研究.