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

一些图的圈划分和路划分

作　者: 杨奉利
导　师: 艾尔肯·吾买尔
学　校: 新疆大学
专　业: 应用数学
关键词: 路(圈)划分路(圈)划分猜想最长路(圈) 支配路(圈)
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 7次
引　用: 0次
阅　读: 论文下载

内容摘要

我们设G为任意图,并且T(G)和c(G)分别定义为图G的最长路的阶数和周长,其中图G的周长c(G)定义如下：如果图G是无边的,则c(G)=1；如果图G是无圈的但至少包含一条边,则c(G)=2；最后,如果图G包含一个圈,则c(G)是图G中最长圈的长度。设一个图G,若对于任意一对满足a+b=τ(G)的正整数(a,b),V有一个划分V=V1和V2满足T(<V1))≤a和丁(<V2>)≤b,则称图G是T-可划分的。路划分猜想(PPC)为：任意图都是T-可划分的。如果c1,c2是正整数,并且V1,V2是满足c(<Vi>)≤ci,i=1,2的V(G)的一个划分,则我们说(V1,V2)是图G的一个(c1,c2)-划分,并且G是(c1,c2)-可划分的。在文献[M.H.Nielsen,On a cycle partition problem,Discrete Math.308(2008)6339一6347]中,Nielsen提出圈划分的猜想：对于任意一对满足c1+c2=c(G)的正整数c1,c2,图G的顶点集V(G)存在一个划分V1和V2，使得集合Vi的导出图的周长至多为ci,i=1,2。在本文中,我们证明：一个图的最长圈是支配圈,则这个图是满足圈划分猜想的,并且我们还证明一个图的最长路是支配路,则这个图是满足路划分猜想的,此外,我们还证明：对于一个图G,如果有c(G)≥|V(G)|-3,则这个图G是圈可划分的。此外,我们证明：如果c1+c2=c(G)和2(|V(G)|-a(G))-c2≤c(G),则G是(c1,c2)-可划分的。

全文目录

中文摘要  2-3
英文摘要  3-5
第一章绪论  5-9
  第一节预备知识  5-7
  第二节本文的主要结果  7-9
第二章图的圈划分  9-16
  第一节相关背景和已知结果  9-11
  第二节主要结果的证明  11-14
  第三节某些条件下的图的圈划分的证明  14-16
第三章图的路划分  16-24
  第一节相关背景和已知结果  16-20
  第二节图的路划分的证明  20-24
结论  24-25
参考文献  25-28
攻读硕士学位期间的研究成果  28-29
致谢  29-30

一些图的圈划分和路划分

内容摘要

全文目录

相似论文