关于图中控制数γL,γt的关系

G（V,E）是一个图且D包含于V,如果N[D]=V,则称D为图G的控制集,进一步,对任一个控制集D1而言均有γ（（D））≤γ（（D1))成立,则称D为图G的小控制集,且小控制数γL（G）=min{|D|:D包含于V且D是G的一个小控制集}。如果点集S包含于V,A↓X∈V均有N（X）∩S≠φ或∪↑x∈SN（x）=V,则称S为图G的全控制集,且全控制数γ1（G）=min{|S|:S是G的一个全控制集}。     

关于图中控制数γL,γt的关系

G（V，E）是一个图且D包含于V，如果N[D]=V，则称D为图G的控制集，进一步，对任一个控制集D1而言均有γ（（D））≤γ（（D1))成立，则称D为图G的小控制集，且小控制数γL（G）=min{|D|:D包含于V且D是G的一个小控制集}。如果点集S包含于V，A↓X∈V均有N（X）∩S≠φ或∪↑x∈SN（x）=V，则称S为图G的全控制集，且全控制数γ1（G）=min{|S|:S是G的一个全控制集}。     

几类图的负对控制数

设D V是图G=(V,E)的任意一个对控制集,如果一个函数f:V→{-1,0,1}满足条件1)对任意点v∈D,有f(v)=1,对任意点v∈V-D,有f(v)≤0,2)对任意点v∈V,均有f(N[v])≥1,则称函数f为图G的负对控制函数。负对控制函数f的重量f(V)是V中所有点的函数值之和,图G的负对控制数γp-(G)=min{f(V)|f是图G的负对控制函数}。本文研究一些图的负对控制数。     

关于图的负对控制数的界

设D真包含V是图G=(V，E)的任意一个对控制集。如果一个函数f：V→{-1，0，1}满足条件：(1)对任意点u∈D，有f(v)=1，对任意点v-D，有f(v)≤0；(2)对任意点v∈V，均有f(N[v])≥1；则称函数f为图G的负对控制函数。负对控制函数f的重量f(V)是v中所有点的函数值之和，图G的负对控制数γp^-(G)=min{f(V)|f是图G的负对控制函数}.本文研究了图的负对控制数的界。     

一类哈密顿图的控制数的上界

设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14.     

单圈图的k-距离匹配控制数

单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(G)是G的一个k-距离控制集且导出子图〈D〉有完美匹配,则称D是G的一个k-距离匹配控制集.k-距离匹配控制数γkp(G)是G的最小k-距离匹配控制集的势.主要证明了单圈图k-距离匹配控制数的一个重要引理,由此找到了单圈图k-距离匹配控制数的上界,并构造了极图.     

关于一些特殊图类的弱控制多项式的研究

研究一些特殊图类的弱控制多项式.令图G=(V(G),E(G))是一个简单连通图，若对任意v∈V(G),存在u∈V(G),使得uv∈E(G)且d(u)≥d(v)成立，则称v弱控制u.设W(G)?V(G),如果对任意u∈V(G)W(G),存在v∈W(G),使得v弱控制u,则称W(G)为图G的一个弱控制集.含点数最少的弱控制集称为最小弱控制集，最小弱控制集中所包含点的个数称为图G的弱控制数，记为γ_wd(G).图G的弱控制多项式为WD(G,x)=■Wd(G,j)x^印j,其中Wd(G,j)表示图G中阶为j的弱控制集的个数.     

一些卡方积图的符号星控制数

设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{+1,-1},对一切v∈V(G)满足∑e∈E(v)f(e)≥1成立,则称f为图G的一个符号星控制函数。图G的符号星控制数定义为γ’ss(G)=min{∑e∈E(v)f(e)∣f为G的符号星控制函数}。在图的符号星控制概念的基础上,确定了两类特殊图的符号星控制数。     

关于图的符号边控制数的一些结论

设G=（V,E）是一个非空图,一个函数f:E→{-1,1},如果满足∑e’∈N[e ]f（e’）≥1对于每一条边e∈E（G）均成立,则称f为图G的一个符号边控制函数。图G的符号边控制数记为r’_s（G）,定义为r’_s（G）=min{∑e∈E（G） f（e） | f为图G的一个符号边控制函数}。本文对图的符号边控制函数进行了研究,得到了图的符号边控制数的一个新的下界;并且确定了圆梯P₂×C_n的符号边控制数。     

图的最小符号控制函数的充要条件

在图G=（V,E）的顶点集V上定义一个二值函数f=V→{-1,1},使对任何v∈V,f(N[v])≥1,则称f是图G的一个符号控制函数。图的符号控制函数的权重定义为f(V)=∑v∈vf(V),它的最小权重称为图的符号控制数,记为γs(G）达到最小权重的符号控制函数称为图的最小符号控制函数,本文讨论最小符号控制函数的必要条件。     

关于图的减控制数

图G=（V，E），一个函数f：V（G）→{-1，0，1}称为G的减控制函数当且仅当对任意v∈V有∑u∈N[V]f （u）≥1．令f（V）=∑v∈Vf（v）为f的权．图G的减控制数γ^-（G）=min{f（V）│f是一个减控制函数}．建立了几类特殊图的减控制数的值，并对一般图讨论了γ^-（G）的界．     

禁用两个子图的图的全控制数

设G=V(V,E)是一个简单无向图.一个点悬挂三个一度点的图称为爪图,D图是一个三角形其中两个点各悬挂一条长为2的路.如果图G的任何导出子图都不同构于爪图也不同构于D图,则称G为无爪和无D图.设S是V的非空子集,如果不在S的点一定与S中的某个点相邻,则称S为G的控制集.如果G中的点一定与S中的某个点相邻,则S称为G的全控制集.最小全控制集包含顶点的数目称为全控制数.给出了当G是N阶连通的无爪和无D图时全控制数紧的上界.     

一些特定图类的严格强控制数

设图G＝(V,E),对于函数f:V→{-1,1},记f的权重f(V)＝∑v∈Vf(v),对v∈V,记f[v]＝∑u∈N[v]f(u).图G的严格强控制函数是f:V→{-1,1}使得对V中多于一半的顶点v有f[v]≥1,图G的严格强控制数是G的所有严格强控制函数的量小权重,且用smaj(G)表示.本文决定了一些特定图类的严格强控制数.     

n-C4的全符号控制数

G=(V,E)是有限简单连通图,用V(G)和E(G)分别表示G的顶点集和边集.f是一个从V(G)∪E(G)→{-1,1｝的函数.f的权重定义为w(f)=∑x∈V(G)∪E(G)f(x).图G的全符号控制函数f:V(G)∪E(G)→{-1,1}是一个对所有的x∈V(G)∪E(G),都满足f[x]≥1的函数,其中f[x]=∑y∈NT[x]f(y).G的全符号控制数γ*s(G)定义为γ*s(G)=min{w(f)│f是G的全符号控制函数｝.Cm表示m个顶点的圈,n-Cm表示恰有一条公共边的n个Cm的拷贝.本文给出了n-C4的全符号控制数.     

pq阶Cayley图的符号星控制数

设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{-1,1},满足f(E(v))≥1,v∈V(G),则称f为图G的一个符号星控制函数.图G的符号星控制数定义为:γss(G)=min{f(E)|f为G的反符号星控制函数},论文确定了pq(2pq,且p、q为互异的素数)阶群Q上Cayley图X(Q,M)的符号星控制数γss(X(Q,M))=(p-1)q+1,M表示群Q的极小生成集.     

关于点赋权图的赋权控制数的一个上界

点赋权图Gw=（V,E,W）是指对简单图G的顶点集作一个赋权函数W：V→R^＋。在图G所有的控制集D V（G）（V（G）／D中的任意顶点v都与D中的点关联）中最小的权和W（D）称为图Gw的赋权控制数。记作γw（Gw）。证明了对基数为N,平均权为W^-的图Gw,其赋权控制数γw（Gw）≤Nw^-1δ＋1^——1＋1n（δ＋1）。     

两类Mycielski图的符号圈控制数

设G=(V,E)是一个图,一个函数f∶E→{-1,1}如果对G中每一个无弦圈C均有f(E(C))≥1,则称f为图G的一个符号圈控制函数,图G的符号圈控制数定义为γ′sc(G)=min{e∈E(G)Σf(e)f为G的符号圈控制函数}.通过研究Mycielski图的符号圈控制数,确定了由路和圈构成的Mycielski图的符号圈控制数.     

图的有效符号边控制数

设G=(V,E)是一个非空图,若函数f:E→{-1,1}对?e∈E(G)均有∑f(e′)=1e′∈N[e],则称f为图G的一个有效符号边控制函数.图G的有效符号边控制数记为rs′e(G),定义为rs′e(G)=min{∑f(e)|f为图Ge∈E(G)的一个有效符号边控制函数}.在本文中,我们给出了一般图的有效符号边控制数存在的必要条件和一个下界,并且证明了图Pm×Cn不存在有效符号边控制函数,最后给出了立方图的有效符号边控制数存在的充要条件.     

图的反符号边全K-控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1}如果∑e′∈N(e)f(e′)≤0对于至少k条边e∈E成立,则称f为图G的一个反符号边全k控制函数。一个图G的反符号边全k控制数定义为γkst(G)=max{∑e∈Ef(e)|f为图G的反符边全k控制函数}。本文主要给出了连通图G的反符号边全k控制数γkst(G)的若干上限。     

图中控制数的有关结论

令G=(V,E)是一个图,点集S V,如果满足N[S]=V(G)(或N(S)=y(G)),则称点集S是一个控制集(或伞控制集).一个连通图G如果满足:对任何不相邻于一次点的v点,G-v的全控制数小于G的全控制数,则称图G是一个γt-临界图.给出连了通无爪3-正则图G的控制数满足γ(G)≤3-n.同时找到一个直径是2的4-γt-临界图.