论文部分内容阅读
在过去的三十多年里,随着计算机科学的迅速发展,图论也得到了飞速发展,而图的横贯理论的研究是图论中发展较快的几个领域之一.图的横贯理论能够快速发展的主要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和选址等理论与实践中有着重要的应用背景.其中图的团横贯是是图中重要的一种横贯.
由于,对于大部分图,团横贯数的判定问题均是NP-完全的,所以对团横贯数的上下界进行精确估计以及图的结构性质的刻画是人们很感兴趣的问题,这对于设计相应的近似算法有重要的实际意义.本文主要研究了几类图上的团横贯数,其相应的结果分为以下三部分:
第一部分,首先得到了立方图上的团横贯数的上下界,并对达到下界的立方图进行了刻画,另外得到了无爪立方图上的一个紧的上界,并在无爪立方图中把团横贯数与匹配数进行了比较.最后我们证明了无爪立方图是弱2-可着色的.(此结果被 Lecture Notes in Computer Science录用)
第二部分,给出了外平面图中团横贯数的上界,以及几类特殊平面图上的上界.
第三部分,我们给出了图的团图为树的这样一类图的上界,并把结果推广到了图的团图为偶图的这样一类图,并且由此结果我们找到了一类满足γ(G)≤n/k的一类图. (有关结果被《J.Shanghai University》录用)