论文部分内容阅读
图的连通支配问题是近几年来图论中的一个比较活跃的研究领域。图的连通支配问题的研究不仅具有很重要的理论意义,而且在优化理论、通讯网络设计与分析、网络搜索、模式识别等许多领域也有很广泛的应用。自1979年E.Sampathkumar和H.B.Walikar提出连通支配的概念以来,针对连通支配问题人们展开了大量的研究,主要集中在两个方面:一个方面是算法的研究及应用,另一个方面是连通支配数性质的研究。同时,由连通支配引出的全支配、临界支配、独立支配、树支配等相关概念,也引起人们的广泛关注和研究。广义Petersen图和循环图C(n;{1,k})的连通支配数、树支配数问题至今尚未完全解决,本文主要运用计算机计算和数学推理证明相结合的方法,针对广义Petersen图P(n,k)和循环图C(n;{1,k})的连通支配数和树支配数进行了研究,得到如下结论:对任意的k≥1,n≥4,P(n,k)的连通支配数和树支配数为:γc(P(n,k))=γtr(P(n,k))。当k=1,n≥4时,γc(P(n,1))=γtr(P(n,1))=n。当k=2,n≥5且为奇数时,γc(P(n,2))=γtr(P(n,2))=n-1。当k=2,n≥6且为偶数时,γc(P(n,2))=γtr(P(n,2))=n。当k=4,n≥17时,γc(P(n,4))=γtr(P(n,4))=n-1。当k=6,n≥25时,γc(P(n,6))=γtr(P(n,6))=n-1。当k=8,n≥33时,γc(P(n,8))=γtr(P(n,8))=n-1。根据k=4,6,8的结论,本文给出了一个猜想:对任意偶数k≥4,n≥4k+1,γc(P(n,k))=γtr(P(n,k))=n-1。对任意的k≥1,n≥5,C(n;{1,k})的连通支配数和树支配数的下界为:γc(C(n;{1,k}))≥[(n-2)/3],γtr(C(n;{1,k}))≥[(n-2)/3]。当k=2,n≥5时,γtr(C(n;{1,2}))=[n/2]-1。当k=3,n≥7时,