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