论文部分内容阅读
图的控制理论是图论中的一个重要分支,在编码理论,计算机科学,通信网络,社会网络等学科中都有广泛的应用。随着计算机科学兴起及函数方法的加入,使得图的控制理论成为图论近几十年发展最快的领域之一.1998年美国图论学者Haynes等人出版了两部专著,较为系统地综述了几千篇关于函数控制数的研究成果.
本文所做工作主要包括以下二个部分:(1)确定几类函数控制数的界(2)某些特殊图的函数控制参数值的确定.
★在第一章,我们给出了本论文要用的相关概念及图的函数控制数的研究概况.
★在第二章,我们得到了图的反符号圈控制数的上界,并且给出了几种特殊图的反符号圈控制数,主要得到了下面几个结果:
·对任意的图G都有γ1rsc(G)≤2|V(G)|-|E(G)|-2且等式成立当且仅当G是树.
·γ1rsc(Kn)=2[n/2]-(n2).
·γ1rsc(Wn+1)=-2[n/4].
·γ1rsc(Kn,m)=mn-min{(m-1)n,m(n-1)}.
★在第三章,给出了图的分数划分数的界:
·对任意一个n阶图G,均有γf(G)df(G)≤n.
·对任意一个最小度为δ的图G,均有δ≤df(G)≤δ+1.
★在第四章,通过反证法及构造全符号函数的方法给出了完全图的全符号控制数的精确值:γ*s(Kn)=[n/2].
★在第五章,给出图的全减符号控制数的上界.应用图的距离为2的减符号控制数与其细分图的全减符号控制数相等的性质给了路的全减符号控制数的精确值.并且给出圈的全减符号控制数的精确值.