论文部分内容阅读
图的控制理论是图论中的一个重要分支,在编码理论,计算机科学,通信网络,社会网络等学科中都有广泛的应用.随着计算机科学兴起及函数方法的加入,图的控制理论成为图论近几十年发展最快的领域之一,而图的强符号控制数有着许多重要的应用背景,因此确定其下界有重要意义.
本文所做的工作主要包括以下四个部分:
在第一章,我们给出了本论文要用的相关概念以及图的控制数的研究概况.
在第二章,指出了文献[2]定理5的错误,改进了文献[7]定理4的下界,得到了图的强符号控制数的3个独立可达的下界,主要结果如下:★对任意连通的n阶图G,若|E(G)|=m,则有γss。(G)≥「5n-2m/4(」),这个界是可达的,C3∪Pn(2≤n≤5)TnR(2≤n≤5)K5都是达到其下界的图.★对任意连通的n阶图G,若|E(G)|=m,则有γss(G)≥2「1+√2m+3n/2(」)-n,偶阶的完全图是达到其界值的图.★对任意连通的n阶图G,若δ、△为最小、最大度,则有γss(G)≥「δ-△+4/δ+△+2 n(」),偶阶的完全图是达到其界值的图.
在第三章,在图的符号控制数基础上提出了图的强符号全控制数并对其进行了研究,给出了圈、轮图、完全图、完全二部图的强符号全控制数的精确值,得到了一般图的强符号全控制数的5个可达下界,主要结果如下:★γtss(G)≥2「m+n/△(」)-n.★γtss(G)≥2「(δ+2)n/δ+△(」)-n.★γtss(G)≥2「(n+m)/δ(」)+n.★γtss(G)≥2「4-δ+√(δ-4)2+8n(δ+2)/4(」)-n.★γtss(G)≥2「2+√4+2m+2n/2(」)-n.
在第四章,在符号圈控制数的基础上提出减圈控制数,给出了一般图的减圈控制数的界以及几类特殊图的减圈控制数的精确值,主要结果如下:★对于任意的n阶图G,均有γmc(G)≥1-n,等号成立时当且仅当G为树.★令M={G1,G2,…,Gm,…},其中G1=K3,Gm表示在Gm-1的任意一个面F内添加一点且连接F边界上的三个顶点所得的图(注意F的边界为三角形),则对于M中的任意一个n阶图G,均有。(G)=n-2.★对于任意的正整数2≤n,m,都有γmc(Km,n)=mn-m-n+1.