论文部分内容阅读
在近四十年里,随着计算机科学的迅速发展,图论的发展也非常迅猛,其中图的控制数理论是图论中发展最快的几个领域之一.控制数理论能够快速发展的主要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社会网络等理论与实践中有着重要的应用.随着研究的深入和应用的激发,各种新的控制参数不断涌现.其中图的函数(全)控制数就是(全)控制数的一类自然推广.由于函数的引入,致使利用函数性质来研究控制数成为可能.目前,函数控制数已成为图的控制理论中一个崭新而富有挑战的研究方向.
在图论中,为了研究图的性质,人们引进了图的邻接矩阵,关联矩阵,距离矩阵,拉普拉斯矩阵等各种矩阵.代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来.而各种矩阵中,很重要的就是图的拉普拉斯矩阵.因为拉普拉斯矩阵的特征值与图的很多不变量有着密切的联系.正如Mohar<[1]>所说:图的拉普拉斯矩阵的特征值更能反映它的图论性质.所以,对图的拉普拉斯矩阵的特征值的研究也越来越受到人们的广泛关注.
本文主要研究了全控制数和符号全控制数的N-G型不等式,以及图上几类全控制参数与拉普拉斯特征值的关系,其相应的结果分为以下两个部分:
第一部分,研究了图上符号全控制数γ<,t>的Nordhaus-Gaddum型不等式,给出了路与其补图的符号全控制数和的上界,以及图与其补图的符号全控制数和的下界. (有关结果被《运筹学学报》录用)
第二部分,给出了连通图上代数连通度α(G)关于全控制数γ<,t>(G)的两个上界,并对第二个上界给出了达到此上界的图的刻画.给出了代数连通度关于符号全控制数γ<,t>(G)以及符号控制数γ<,s>(G)的上界,并证明了界是紧的(有关结果已投《Czechoslovak Mathematical Journal》杂志).最后给出了任意图上和正则图上拉普拉斯谱半径λ(G)关于符号控制数的下界,并给出了刻画,另外对拉普拉斯谱半径关于符号全控制数的下界进行了讨论.