论文部分内容阅读
近三十多年来,随着计算机科学和网络通讯技术的飞速发展,图论研究也呈现出异常活跃的趋势,而控制数理论也许是其中发展最快的领域.图的控制数理论作为图论的一个重要研究方向,在相关学科领域,例如计算机科学、通讯网络、编码理论、运筹学以及社会学等领域具有广泛的应用.目前,关于图的控制数理论研究主要集中在四个方面:(1)各类控制参数的界的确定,相互之间关系的研究,以及控制参数与图的其他参数,如色数的关系研究;(2)各类控制参数计算复杂性的研究及其算法的设计;(3)函数控制数及其相关课题的研究;(4)控制数理论在相关学科中的应用研究.
本文所做的工作主要包括以下五部分:第一,我们确定了一般连通图及无爪立方图上电力控制数的准确上界,并对达到其上界的极值图进行了刻画(有关结果已被《DiscreteMathematics》录用);并分别讨论了外平面图及一般平面图上电力控制数的界(有关结果已被《JournalofShanghaiUniversity》录用).
第二,我们研究了两类新的控制函数:负边控制函数和负星控制函数;确定了负边控制数的界,并对达到其上界的阶数为偶数的极值图进行了刻画;并且讨论了这两类控制参数与其他控制参数的关系(有关结果已被《ArsCombinatoria》录用).
第三,我们对达到图的2-距离控制数已知上界的极值图进行了完全刻画.第四,我们给出了二部置换图上无圈控制集的线性时间算法,并研究了三种情况下直线簇上区间图的最小连通控制集算法(有关结果已发表在《上海大学学报(自然科学版)》).
第五,我们构造了具有最小可能边数且最小度为k的任意大的无限唯一k-可着色图类(有关结果已被《JournalofShanghaiUniversity》录用).