若干图的等全着色及彩虹支配问题的研究

论文摘要

图的等全着色是图的着色问题中的难题之一。对图的等全着色问题的研究不仅具有重要的理论意义，而且在安排课表、频率分配等领域有很广泛的应用。图的彩虹支配问题是图的支配问题中比较活跃的研究领域之一。图的彩虹支配问题的研究在优化理论、通讯网络设计与分析、网络搜索、模式识别等许多领域有很广泛的应用，对其研究具有现实意义。目前国内外已有结果给出对于最大度不超过3的图的等全着色数小于等于5的界，还给出路径、圈、太阳图的2-彩虹支配数的精确值，但未给出广义Petersen图P（n,2）和P（2k+1，k）的2-彩虹支配数的精确值。本文主要通过计算机计算及数学推理相结合的方法，研究了图的等伞着色及2-彩虹支配问题。对3-正则图如Flower snark及其相关图、Goldberg snark及其相关图、TwistedGoldberg snark及其相关图和Blanu（?）a snark图的等全着色进行研究。给出这些图的等全着色数为4．本文还对广义Petersen图P（n,2）和P（2k+1,k）的2-彩虹支配问题进行研究。给出对于所有的n，广义Petersen图P（n,2）的2-彩虹支配数的精确值为：而对于任意k≥2时，广义Petersen图P（2k+1,k）的2-彩虹支配数为：还给出广义Petersen图P（n,2）的2-彩虹支配方式。

论文目录

• 摘要
• Abstract
• 引言
• 1 基本概念
• 1.1 图
• 1.2 路与图的连通性
• 1.3 正则图与完全二部图
• 1.4 子图与生成子图
• 1.5 导出子图与边导出子图
• 1.6 图的同构
• 1.7 弦图、n-太阳图
• 2 图的等全着色和彩虹支配问题进展
• 2.1 图的等全着色问题及进展
• 2.1.1 着色的起源及发展
• 2.1.2 着色的基本概念
• 2.1.3 着色的计算复杂性
• 2.1.4 着色的应用
• 2.1.5 等全着色的发展
• 2.2 图的彩虹支配问题及进展
• 2.2.1 支配的起源及发展
• 2.2.2 支配的基本概念
• 2.2.3 支配的计算复杂性
• 2.2.4 支配集的应用
• 2.2.5 彩虹支配的发展
• 2.3 本文工作
• 3 若干snark及其相关图的等全着色问题
• k的等全着色'>3.1 Flower snark及其相关图F_k的等全着色
• k^*的等全着色'>3.2 图F_k^*的等全着色
• k与Twisted Goldberg snark及其相关图G_k^*的等全着色'>3.3 Goldberg snark及其相关图G_k与Twisted Goldberg snark及其相关图G_k^*的等全着色
• k¹的等全着色'>3.4 Type 1 Blanu（?）a snark图B_k¹的等全着色
• k²的等全着色'>3.5 Type 2 Blanu（?）a snark图B_k²的等全着色
• 4 广义Petersen图P（n,2）彩虹支配问题
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢