论文部分内容阅读
在过去的三十多年里,随着计算机科学的迅速发展,图论也得到了迅速发展,而控制数理论的研究是图论中发展最快的几个领域之一.随着研究的深入和应用的激发,各种新的控制参数不断涌现.其中图的函数控制数就是控制数的自然推广.由于函数的引入致使利用函数性质来研究控制数成为可能.目前,函数控制数已成为图的控制理论中一个崭新而富有挑战的研究方向.对一般图而言,几乎所有的函数控制数的判定问题均是NP完全的,所以对它们的上下界进行精确估计以及图的结构性质刻画是人们很感兴趣的问题,这对于设计相应的近似算法也有重要的实际意义。
Harris[21]等人引入图的上负全控制数的概念.f:V(G)→{-1,0,1}称为图G的负全控制函数,如果对任意点V∈V,均有F[v]≥1,其中f[v]=∑v∈N(v).如果对每一个点V∈V,不存在负全控制函数g:V(G)→{-1,0,1},g≠f,满足g(v)≤f(v),则称f是一个极小负全控制函数.图的上负全控制数Γ-1(G)=max{ω(f)|f是G的极小负全控制函数},其中ω(f)=∑v∈(G)f(v).本文主要研究了函数的上负全控制数,其相应的结果分为以下两部分:
第一部分,首先介绍了3-正则图,5-正则图的Γ-1(G)的可达上界,接着归纳出度为奇数的正则图的Γ-1(G)的可达上界,并刻画了达到此上界的极图。
第二部分,首先介绍了2-正则图,4-正则图的Γ-1(G)的可达上界,接着对6-正则图的Γ-1(G)的可达上界进行了探试并对度为偶数的正则图的Γ-1(G)的可达上界给出了猜想。