若干类图支配问题的研究

论文摘要

图的支配及其相关问题是近年来图论中一个比较活跃的研究领域,它是由实际应用领域提出来的。研究它不仅有重要的理论意义,而且在通讯网络的设计与分析、社会科学、优化理论、计算的复杂性和算法设计等诸多领域也有广泛的应用。本文对图的支配数（Domination number）及其相关问题即图的Packing数（Packing number）、图的罗马支配数（Roman domination number）以及图的符号边支配数（Signed edge dominationnumber）等问题进行了较深入的研究,取得了较好的成果。图的支配问题是近年来图论领域中的核心问题之一。目前为止仅知道很少的几类图的支配数,例如完全图、完全二分图、路径、圈、星、冠图以及部分笛卡儿乘积图等。本文对图的支配数进行了研究,提出了重复支配数的概念,将计算图的支配数问题转化为计算图的重复支配数问题,从而给出了广义Petersen图P（n,k）（k=2,3）、循环图C（n;{1,k}）（k=2,3,4）的支配数,并给出了广义Petersen图P（n,k）（k为奇数）支配数的一个较好的界。图的Packing数和图的支配数密切相关。Fisher D C对图的Packing数进行了研究,并给出了路径、圈、完全二分图以及完全格图（complete grid graphs）的Packing数。本文给出了广义Petersen图P（n,k）（k=1,2,3）的Packing数以及循环图C（n;{1,k}）的Packing数的一个较好的界。图的罗马支配问题是图的支配相关问题中一个较新的问题。Cockayne E J等研究了图的罗马支配数,给出了路径、圈、完全图、完全二分图的罗马支配数,并证明了如下的几类图是罗马图:当k≥1时,P3k,P3k+2,C3k,C3k+2是罗马图:当min{m,n}≠2时,Km,n是罗马图。本文给出了广义Petersen图P（n,k）（k=1,2,3）、循环图C（n;{1,k}）（k=2,3,4）以及笛卡儿乘积图C5m□C5n的罗马支配数,并证明了当n≥3且n≠2 mod 4时广义Petersen图P（n,1）是罗马图:当n=11或n≥7且n≠3 mod 4时广义Petersen图P（n,3）是罗马图;当n=0 mod 4且0≤k≤「（n-1）/2-1」/2时广义Petersen图P（n,2k+1）是罗马图:当n≥7且n≠4 mod 5时循环图C（n;{1,3}）是罗马图:当n≥4（n≠2k）且n≠1 mod（2k+1）时循环图C（n;{1,2,3,…,k}）是罗马图以及当m,n≥1时笛卡儿乘积图C5m□C5n是罗马图。图的符号边支配问题也是图的支配相关问题中一个较新的问题。徐保根等研究了图符号边支配数,并证明了对任意的n（n≥4）阶图G有,γ5（G）≤「11/6n-1」。本文构造出了一类符号边支配数为γ5(Gm,k)=—k（m-1）（km+k+1）/2（k≥2,m≥1）的k-连通图Gm,k,从而证明了存在一类k-连通图,它的符号边支配数可以任意小。这个结论也证明了徐保根提出的2-连通图的符号边支配数大等于1的猜想不成立。本文所研究的图的支配数及其相关问题属于NP-困难问题,研究它对解决一般NP-困难问题也很有意义。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 基本概念
• 1.2 支配集与支配数
• 1.2.1 支配问题的起源与发展
• 1.2.2 支配数的基本概念
• 1.2.3 支配数的计算复杂性
• 1.2.4 支配集的应用
• 1.3 Packing集与Packing数
• 1.4 罗马支配集与罗马支配数
• 1.5 符号边支配数
• 1.6 本文主要工作
• 2 广义Petersen图、循环图的支配数
• 2.1 广义Petersen图P（n,k）的支配数
• 2.1.1 广义Petersen图P（n,2）的支配数
• 2.1.2 广义Petersen图P（n,3）的支配数
• 2.1.3 广义Petersen图P（n,2k+1）（k≥2）的支配数的上界
• 2.2 循环图C（n;{1,k}）（k≥2）的支配数
• 2.3 小结
• 3 广义Petersen图、循环图的Packing数
• 3.1 广义Petersen图P（n,k）（k=1,2,3）的Packing数
• 3.1.1 广义Petersen图P（n,1）的Packing数
• 3.1.2 广义Petersen图P（n,3）（n≥7）的Packing数
• 3.1.3 广义Petersen图P（n,2）（n≥5）的Packing数
• 3.2 循环图C（n:{1,k}）的Packing数
• 3.3 小结
• 4 罗马支配数
• 4.1 基本性质
• 4.2 循环图C（n;{1,k}）的罗马支配数
• 4.3 广义Petersen图P（n,k）（k为奇数）的罗马支配数
• 5m□C_5n的罗马支配数'>4.4 笛卡儿乘积图C_5m□C_5n的罗马支配数
• 4.5 小结
• 5 符号边支配
• 5.1 一类k-连通图的符号边支配数
• 5.2 小结
• 总结与展望
• 参考文献
• 创新点摘要
• 攻读博士学位期间参加的科研项目和完成的学术论文
• 致谢