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

图的可迹性和直积图着色性质的讨论

作　者: 黄月梅
导　师: 阿勇嘎
学　校: 内蒙古师范大学
专　业: 基础数学
关键词: n-可扩图可迹性直积图柱心收缩
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 23次
引　用: 0次
阅　读: 论文下载

内容摘要

本文第一部分根据三点独立集的度和(记作σ3(G))讨论了n ?可扩图的可迹性.关于n ?可扩图,1957年Berge在文献[2]中首次提出n ?可扩路的问题,而自从Plumer于1980年在文献[3]中首次引入n ?可扩图的概念以来,一些学者对可扩图的度和,可迹性,Hamiltonian性等方面进行研究,得到了一系列成果[3 ? 5].2001年Ken-ichi Kawarabayashi , Katsuhiro Ota and Akira Saito在文献[4]中给出连通的n-可扩图的度和与哈密尔顿性及该图与完全图之间的一些关系.1996年阿勇嘎教授在文献[5]中根据顶点数不小于3的连通图的度和得到图G的子图在G中可迹的一个充分条件.在以上的研究基础上,本文根据图中三点独立集的度和得到了连通的n ?可扩图可迹的一个充分条件.第二部分主要证明了对几类特殊图Hedetniemi猜想的等价命题成立.图论中,图的着色问题是人们关注的一个焦点,着色问题起源于最著名的猜想---四色猜想[6].自从英国人Guthre.F[佛朗西斯.古特里]于1852年提出四色问题之后,人们用不同的方法去攻克这一猜想,但至今还未有严格的解析证明.Hedetniemi在文献[7]中揭示了一个图的色数与直积图色数之间关系的猜想,用代数思想研究图的着色问题.对色数大于5的图还未证明Hedetniemi猜想成立.Benoit Larose, Claude Tardif在文献[11]中用收缩的观点研究Hedetniemi猜想,并证明了对两个连通图和顶点传递的射影的核,Hedetniemi猜想的等价命题成立.本文根据以上研究结果及一个图是柱心的充分条,件证明了对几类特殊的图Hedetniemi猜想等价命题成立.

全文目录

中文摘要  4-5
ABSTRACT  5-8
引言  8-10
第一章 n-可扩图的可迹性  10-18
  1.1 基本概念和引理  10-12
  1.2 主要结果和证明  12-18
第二章 Hedetniemi.S 猜想与图的柱心之间的关系  18-23
  2.1 基本概念和引理  18-21
  2.2 主要结果和证明  21-23
参考文献  23-24
附录  24-25
致谢  25

图的可迹性和直积图着色性质的讨论

内容摘要

全文目录

相似论文