一类笛卡尔积图的交叉数

论文摘要

M. R. Garey and D. S. Johnson已经证明确定图的交叉数是一个NP完全问题（见文献[1]）,因为其难度,我们能够确定交叉数的图类非常少,在许多情况下,即使找出图的交叉数的一个好的上界或下界也是非常困难。目前,很多文献都是在研究一些特殊图类的交叉数,例如:完全图、完全二部图、完全三部图、循环图及一些特殊图类的笛卡尔积图等。本文研究路与某些图类的笛卡尔积图的交叉数。 第一章:交代了本文的写作背景,交叉数研究在国内外发展动态,研究工作的意义以及本文中要解决的问题和创新之处。 第二章:基本概念和性质介绍了阅读本文所需要的预备知识其中主要包括交叉数的概念,并介绍了在后面文章中会出现的一些相关概念,性质以及常用到的一些定理。 第三章:我们寻求了一种好画法,从而给出了路Pm与轮Wn的笛卡尔积交叉数的一个上界即并且证明了当m=1,2,3时的交叉数与此上界是符合的。这里,Pn表示边长为n的路,Wn表示由一点到一个n圈Cn的悬挂,也即从独点K1向Cn的所有n个点分别连一条边所得图。 第四章:我们确定了5个六阶图与路Pn的笛卡尔积图的交叉数。除了每个定理都寻求到一个好画法外,定理1,2的完成是通过交叉数的一个重要性质得到,定理3,4,5的证明是各自独立完成,整个证明思路看似相同,但实际上在各种细节问题上各有独特之处。 第五章:提出了研究工作在发展中的几个问题以及作者在以后将致力于前进的方向。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 第二章 基本概念和性质
• m与轮W_n的笛卡尔积交叉数'>第三章 路P_m与轮W_n的笛卡尔积交叉数
• m×W_n）的上界'>§3.1 cr（P_m×W_n）的上界
• 1×W_n的情形'>§3.2 P₁×W_n的情形
• 2×W_n的情形'>§3.3 P₂×W_n的情形
• 3×W_n的情形'>§3.4 P₃×W_n的情形
• n的笛卡尔积交叉数'>第四章 5个六阶图与路P_n的笛卡尔积交叉数
• §4.1 一些定义和引理
• §4.2 当j=1，2时，定理的证明
• §4.3 当j=3时，定理的证明
• §4.4 当j=4时，定理的证明
• §4.5 当j=6时，定理的证明
• 第五章 结束语
• 参考文献
• 附录
• 攻读硕士学位期间发表的学术论文
• 致谢
• 湖南师范大学学位论文原创性声明