若干图类交叉数的研究

论文摘要

图的交叉数问题,起源于二战期间Pual Tur（?）n在砖厂碰到的一个实际难题,逐渐发展成为图论学科中非常活跃的一个分支,吸引着国内外许多学者的关注.然而,确定一般图的交叉数是一个NP-完全问题,因此,到目前为止有关交叉数的结果比较少,仅限于一些特殊简单图的交叉数.甚至在许多情况下,试图找出图的交叉数的一个好的上界或下界也很困难.本文运用组合方法和归纳思想以及反证法,确定了一些特殊图类,如广义Petersen图P（3k,k）,循环图C（3k-1;{1,k}）,Wm×Pn,两个特殊的六阶图与星Sn的笛卡尔积图,星图Sm与路Pn、星图Sm与圈Cn的联图的交叉数的精确值或者其上、下界,并试图研究交叉数的一般性质,从画法上着手得到了一个好画法为最优画法的充分条件.全文由9个章节组成.第一章较为详细地交代了交叉数的起源,研究工作的理论与实际意义,以及目前交叉数研究在国内外的发展动态.同时还简要介绍了本文的主要结构.第二章介绍了阅读本文所要用到的图的交叉数方面的基本概念和预备知识.第三章得到了当k≥4时,广义Petersen图P（3k,k）的交叉数为k.第四章讨论了当k≥3时,循环图C（3k-1;{1,k}）交叉数的上界和下界.第五章确定了对任意的m≥3和n≥1,轮Wm与路Pn的笛卡尔积图的交叉数.第六章对两个特殊的六阶图与星Sn的笛卡尔积图的交叉数进行了研究.第七章讨论了当m=3,4,5时,星Sm与路Pn的联图的交叉数,和当m=3,4时,星Sm与圈Cn的联图的交叉数.第八章研究图的交叉数的一般性质,并从画法上着手得到了一个好画法为最优画法的充分条件.第九章给出了本文的总结和对未来工作的展望.

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 研究背景介绍
• 1.2 本文的结构
• 2 预备知识和基本概念
• 3 广义Petersen图P（3k,k）的交叉数
• 3.1 一些引理
• 3.2 P（12,4）的交叉数
• 3.3 定理3.1的证明
• 4 循环图C（3k-1;{1,k}）的交叉数
• m×P_n的交叉数'>5 W_m×P_n的交叉数
• n的笛卡尔积图的交叉数'>6 六阶图与星S_n的笛卡尔积图的交叉数
• 1×S_n的交叉数'>6.1 G₁×S_n的交叉数
• 2×S_n的交叉数'>6.2 G₂×S_n的交叉数
• m ∨ P_n与S_m ∨ C_n的交叉数'>7 S_m ∨ P_n与S_m ∨ C_n的交叉数
• 8 一个好画法是最优画法的充分条件
• 9 后记
• 9.1 工作总结
• 9.2 工作展望
• 参考文献
• 附录一 攻读博士学位期间发表或接受发表的学术论文
• 附录二 致谢