正则图的上负全控制数

来源 :华东师范大学 | 被引量 : 0次 | 上传用户:k1389520
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在过去的三十多年里,随着计算机科学的迅速发展,图论也得到了迅速发展,而控制数理论的研究是图论中发展最快的几个领域之一.随着研究的深入和应用的激发,各种新的控制参数不断涌现.其中图的函数控制数就是控制数的自然推广.由于函数的引入致使利用函数性质来研究控制数成为可能.目前,函数控制数已成为图的控制理论中一个崭新而富有挑战的研究方向.对一般图而言,几乎所有的函数控制数的判定问题均是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)的可达上界给出了猜想。
其他文献
本文主要研究了整体pinching定理在调和函数中的应用及Moser迭代技术,由四部分组成。 第一部分扼要的介绍了整体pinching定理的历史,背景以及Moser迭代技术。第二部分给出
本文研究了高斯扰动下的热方程质,并计算其作用泛函。我们首先介绍了高斯噪声以及关于鞅测度的随机积分。在第二章中,我们验证了高斯噪声的大偏差性质。然后,在第三章我们给
竞争失效产品的加速寿命试验是可靠性试验技术的一个重要分支,相关的研究受到了统计学界和可靠性工程界的广泛关注,而贝叶斯统计理论又是统计学中的半边天,所以本文对竞争失
线性回归模型是统计学中最重要的模型之一,其参数的估计有许多良好的性质。但在许多应用问题中,待处理的数据,通常并不像经典回归分析中那样直接测量。或者即使可以直接测量
本文主要研究形如M=Bu(+)N的一类模上的自同态环,其中R为含单位元的环,直和项Ru是M的自由子模。通过研究我们发现,M的自同态环Ω=End(RM)的一个右理想M°可以展开成与M半线性