学位论文 > 优秀研究生学位论文题录展示

一些特殊图的群连通度

作　者: 王可可
导　师: 郝荣霞
学　校: 北京交通大学
专　业: 运筹学与控制论
关键词: 群连通度 4-边连通导出匹配
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 13次
引　用: 0次
阅　读: 论文下载

内容摘要

本文所涉及到的图都是有限图允许有环和重边.当n≥2时,Zn表示的是n阶循环群.令A表示单位元为O的交换群,A*=A-{0}.令F(G,A)为边集E(G)到A上的函数集合,F*(G,A)是E(G)到A*上的所有函数的集合.本文中,设X是E(G)的一个子集,f是：X→A的函数,将f扩充到E(G)→A上的函数,即对所有的e∈E(G)-X,都满足f(e)=0.给定函数f∈F(G,A),令(?)f：V(G)→A为：函数b：V(G)→A若满足∑v∈V(G)b(v)=0,则称其为G上的A-值零和函数.其中Z(G,A)是包括G上所有A-值零和函数的集合.给定图G上的一个定向D和函数b∈Z(G,A),存在函数f∈F*(G,A),若(?)f=b,则记f是G上的(A,b)-处处非零流.若一个图G对任意的b∈Z(G,A),都存在一个定向D,使得图G有(A,b)-处处非零流,则称图G是A-连通的.对任一交换群A,<A>表示所有A-连通图的集合.令图G是一个2-边连通图,其群连通度定义如下：∧g(G)=min{k：对任意交换群A,且|A|≥K,G都是A-连通的}这里已得到若G是一个2-边连通图,则人∧g(G)是一个有限值.Devos在Discrete Math.P306,26-30(2006)中提出的猜想：令图G是一个4-边连通的图,并且它的每一条边都包含在一个长度不超过3的圈中,那么图G一定是Z3-连通的.本文中,在证明交错图AG4的过程中,我们找到了关于Devos猜想的一个反例.令图G是一个简单图,顶点|V(G)|=2n.设F是E(G)的任意子集,即F(?)E(G),记|F|=k.若G-F中的任一匹配都可扩充到它的一个完美匹配上,称G是k-边可删的导出匹配可扩图.第一章主要介绍了交错群网络ANn,交错群图AGn和4-正则,无爪,1-边可删的导出匹配可扩图.轮图,完全图,弦图,三角连通图等的主要定理及相关结论.第二章主要是关于交错群网络AN4,交错群图AG4群连通度的讨论.对交错群网络AN4的证明,首先我们利用收缩的方法限定它的群连通度上界和下界.然后利用反证法证明它的群连通度不等于3.从而得出它的群连通度为4.对于交错群图AG4,用类似交错群网络AN4的证明方法.我们可以得到结论：交错群网络AN4,交错群图AG4的群连通度都为4.第三章是对4-正则,无爪,1-边可删的导出匹配可扩图群连通度的证明,我们通过其图中任一顶点的邻点之间所含边的条数来进行讨论.我们证明了结论：4-正则,无爪,1-边可删的导出匹配可扩图的群连通度为3.第四章是对本文的总结以及留待解决的问题.包括关于对交错群AGn和交错群图ANn的讨论.

全文目录

致谢  5-6
中文摘要  6-8
英文摘要  8-11
第1章绪论  11-22
  1.1 引理  12-13
  1.2 部分已知特殊图类的群连通度  13-19
  1.3 三类图的定义  19-22
第2章交错群网络和交错群图的群连通度  22-32
  2.1 交错群网络AN_4的群连通度  22-26
  2.2 交错群图AG_4的群连通度  26-32
第3章一边可删的导出匹配可扩图的群连通度  32-45
第4章小结  45-46
参考文献  46-48
作者简历  48-50
学位论文数据集  50

一些特殊图的群连通度

内容摘要

全文目录

相似论文