关于图中控制数γ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的一个全控制集}。     

树图的全控制数

设G为n阶连通图，集合S称为图G的全控制集，如果V（G）的每个顶点都和S中某点相邻。图G的全控制数，记为γt（G），是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1，n-1的树T，γt（T）=min{（2n/3），n-l，[n/2]＋l-1}，这里l表示树T中叶子的数目。     

路与圈的笛卡尔乘积的全控制数

令图G是无孤立点的无向图.V(G)是图G的顶点集,D是V(G)的真子集.如果图G的每一个顶点至少与集合D中一点相邻,则集合D是图G的全控制集.G中最小全控制集的顶点数称为G的全控制数,记为γt(G).参考已有全控制数的知识及笛卡尔乘积Cm□Cn、Pm□Pn的全控制数的相关结论,利用γt(Cm□Cn)≤γt(Pm□Cn)≤γt(Pm□Pn)这一不等式给出了Cm□Pn(m=3,4)、Pm□Cn(n=2,4)的全控制数.     

一类环的单位图的控制数

对于一个具有单位元的环R,R的单位图记为G(R).它的顶点是R中的元素,两个不同的顶点x和y相连当且仅当x+y是环R的单位.设G是一个图,V是G的顶点集,D是V的一个子集,若对于V\D的任一点,都存在D中至少一点与之相连,则称D是G的一个控制集,含有顶点数最少的控制集称为图G的一个γ-集,所含的顶点个数称为G的控制数.该文主要研究一类有限环的单位图的控制数,完全确定了当有限交换环R的直和分解恰好是3项时,环R的单位图的控制数.     

赋权图过指定点的圈

设G是满足条件D1和D2的2-连通非Hamilton赋权图,证明了如下新结果：若G满足dw（x）＋dw（y）≥m（xy不属于E（G）,x≠y）,则通过图G的每个顶点存在权重大于或等于m的圈.该结果推广了非赋权图的已有结果.     

关于图的距离控制数的上界

对于任意的正整数l,连通图G的顶点子集D被称为距离l 控制集 ,是指对于任意顶点v D ,D中至少含有一个顶点u ,使得距离dG(u ,v) ≤l.图G距离l 控制数γl(G)是指G中所有距离l 控制集的基数的最小者 .确定图G的距离l 控制数γl(G)是NP 问题 .给出了当G是阶数为p (p ≥l 1 )的连通图时 ,对于任意的正整数l,都有最优上界γl(G)≤ p-Δ l - 1 l .而且针对某些Δ和l,是对Meir和Moon的结果的一种改进     

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

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

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

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

图中控制数的有关结论

令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-临界图.     

图的独立数与分数一致性

设G是一个顶点集为V（G）,最小度为δ（G）,独立数为α（G）的图, k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V（F）都有dhG（x）＝k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ（ G）≥k＋2,且α（ G）≤4k（δ-k-1）（k＋1）2,则图G是一个分数k一致图。     

图的反符号边全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)的若干上限。     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

强全控制边临界图

不含孤立点的图G称为全控制边临界的,如果对任意两个不相邻顶点u和v, 有γt(G uv)<γt(G).也称这样的图为γt-临界的. 如果该图G的全控制数为k,称G为k-γt-临界的.一个γt-临界图G称为强γt-临界的, 如果对任意顶点v∈V(G)存在G的一个基数为γt(G)-1的控制集D使得G[D]除v外不含孤立点.研究了强γt-临界图的性质,给出了一个由小的强γt-临界图构造大强γt-临界图的方法.     

图的反全符号控制数

设G=（V,E）是一个非空图,对于一个函数f∶V（G）∪E（G）→{-1,1},则称f的权重为w（f）=∑x∈V（G）∪E（G）f（x）。若x∈V（G）∪E（G）,定义f[x]=∑y∈NT[x]f（y）。如果对所有的x∈V（G）∪E（G）都有f[x]≤1,则称f是图G的一个反全符号控制函数。G的反全符号控制数定义为γ＊...     

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

设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的符号星控制函数}。在图的符号星控制概念的基础上,确定了两类特殊图的符号星控制数。     

强乘积图与字典乘积图的控制数

证明了:1)图G和H的强乘积图GH的控制数γ(GH)≤γ(G)γ(H),并举例说明此上界是可以达到的;2)若γ(H)=1,则G与H的字典乘积图的控制数γ(G H)=γ(G);若G不含孤立点并且γ(H)≥2,则γ(G H)=γt(G),其中γt表示图的全控制数.     

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

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