论文部分内容阅读
图的支配问题是近年来图论中一个比较活跃的研究领域。图的支配问题的研究不仅具有很重要的理论意义,在优化理论、通讯网络的设计与分析、社会科学、计算复杂性和算法设计等许多领域也有很广泛地应用。本文研究了广义Petersen图P(n,k)的连通支配数和树支配数以及几类支配临界图的一些性质,其中包括Hamilton性质、最小边数和直径。连通支配集在网络设计中有许多应用。树支配集是一类特殊的连通支配集。本文研究了广义Petersen图P(n,k)的连通支配数和树支配数,证明对任意的广义Petersen图P(n,k),它的连通支配数和树支配数是相等的,并且确定了k=1,2,4,6,8,n/2时,广义Petersen图P(n,k)的连通支配数和树支配数的值。Hamilton性质是图的一个重要性质。Wojcicka证明了3-边支配临界图有Hamilton路并猜想任意的(k-1)-连通k-边支配临界图有Hamilton回路。本文把具有Hamilton路的图类从3-边支配临界图扩展到3-(γ,2)-边临界图,同时构造出一类3-连通4-边支配临界的非Hamilton图,从而证明了Wojcicka上述猜想不成立。一个图的边数对应其所代表的网络连线的数目。本文研究了边支配临界图和局部边支配临界图的最小边数。本文构造了几类边支配临界图和局部边支配临界图,给出了边支配临界图和局部边支配临界图的最小边数的一个上界。图的直径和网络的传输延迟有密切的关系。本文构造了直径为2的既是k-顶点支配临界的,又是k-顶点全支配临界的图,这个结果解决了Goddard等人提出的一个公开问题。本文还研究了点支配临界图,给出了无临界点的4-点支配临界图和4-全点支配临界图的直径。最后,本文研究并给出了边连通支配临界图的直径。