图的反符号边k-控制数

图的符号边控制数有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其精确值有重要意义.本文给出了一般图的反符号边k-控制数的若干上界.

关于图的反符号星控制数

引入了图的反符号星控制的概念,设G=(V,E)是一个没有孤立点的图,一个函数f:E→{+1,-1}对一切点v∈V(G)所在的星中的边e有∑f(e)≤0成立,则称f为图G的一个反符号星控制函数.而γr′ss(G)=max{∑f(e)|f为图G的反符号星控制函数,e∈E(G)}称为图G的反符号星控制数.我们主要给出了图的反符号星控制数的上界,并确定了完全图与完全二部图的反符号星控制数.

关于图的反符号圈控制数

引入了图的反符号圈控制的概念,设G=(V,E)是一个非空图,一个函数f:E→{+1,-1}对G中每一个无弦圈C均有∑e∈E(C)f(e)≤0成立,则称f为图G的一个反符号圈控制函数,而γ′rsc(G)=max{∑e∈E(G)f(e)|f为图G的反符号圈控制函数}称为图G的反符号圈控制数。给出了图的反符号圈控制数的界限,刻画了满足γ′rsc(G)=-|E(G)|+2的所有连通图G,并且确定了图与补图以及几类特殊图的反符号圈控制数。

图的反符号全控制数

设G=(VE)是一个无孤立顶点的图,一个函数f:V{-1,+1}称为图G的一个反符号全控制函数,如果f(N(v))≤1对任何点v V(G)成立。图G的反符号全控制数记为γrst(G)=max{f(V)|f为图G的一个反符号全控制函数}。该文对图的反符号全控制函数进行了研究,获得了一般图的反符号全控制数的若干界限,确定了完全图和完全二部图的反符号全控制数。

关于图的反符号路控制研究

引入了反符号路控制的概念,得到了任一图G的反符号路控制数γr′P(G)的若干上界,并确定了一些特殊图的反符号路控制数的确切值.

关于图的反符号边控制

引入了图的反符号边控制的概念,设G=(V,E)是一个图,一个函数f:e→{-1,+1}如果对任意e∈E(G),均有∑e′∈N[e]f(e′)≤0,则称f为图G的一个反符号边控制函数.图G的反符号边控制数定义为-γs(G)=max{∑e∈Ef(e)|f为图G的反符号边控制函数}.在本文中,我们主要给出了图的反符号边控制数的两个上界,并确定了几类特殊图的反符号控制函数.

关于图的反符号圈控制数

本文研究了图的反符号圈控制的问题.利用分类和反证的方法,获得了满足反符号圈控制数为负边数加4的连通图的刻画和完全二部分图的反符号圈控制数.

图的反符号星k控制数

设G=(V,E)是一个图,一个函数f:E→-1,+1如果∑f(e)≤0 e∈E[v]对于至少k个顶点v∈V(G)成立,则称f为图G的一个反符号星k控制函数,其中E(v)表示G中与v点相关联的边集.图G的反符号星k控制数定义为γrkss(G)=max{∑f(e) e∈E│f为图G的反符号星k控制数}。得到了一般图的反符号星k控制数的若干上界,对文[6]中的结果进行了推广,还确定了路Pn和圈Cn的反符号星k控制数。

pqr阶Cayley图的反符号星控制数

当群Γ的换位子群Γ的阶数为qr时,根据图的反符号星控制数的概念,确定了pqr阶群Γ上Cayley图X(Γ,M)的反符号星控制数γrss(X(Γ,M)),其中2<p<q<r,且p,q,r为互异的素数,M表示群Γ的极小生成集.

关于图的反符号全控制

设G=(V,E)是一个图,一个函数f:V∪E→{-1,+}1,如果对每一个x∈E∪V,都有∑y∈Nt[x]f(y)≤0成立,则称f为图G的一个反符号全控制函数,其中Nt(x)表示G中与元素x相邻或相关联的元素之集,称为元素x的全邻域,Nt[x]=N(x)∪{x}为x的闭全邻域。规定图G的反符号全控制数定义为γrst(G)=max{∑x∈V∪Ef(x)f为图的反符号全控制函数}。得到了一般图的反符号全控制数的若干上界,并确定了圈Cn的反符号全控制数。

图的符号k-控制

设G(V,E)为一个图,k为任意的正整数且k不超过|G|,若有一个函数f:V{1,-1}满足:V中至少有k个点满足f[v]1,则称f为图G的一个符号k-控制函数,图G的符号k-控制数定义为γ-ks11(G)=min{f(V)|f为图G的一个符号k-控制}.给出了图的符号k-控制数的下界的一个改进的结论,并确定了轮图的符号k-控制数.

图的反全符号控制数

设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的反全符号控制数定义为γ*rs(G)=max{w(f)|f是图G的一个反全符号控制函数}。本文得到了图的反全符号控制数的2个上界,并研究了路Pn和星图K1,n的反全符号控制数。

图的反符号圈控制

为丰富图的控制理论,引入了图的反符号圈控制的概念.通过对图的结构分析,给出了阶数为n、边数为m的简单图的反符号圈控制数的一个紧的上界.对一些特殊图类,通过给出具体的反符号圈控制函数的方法,给出了反符号圈控制数的精确值.

图的反符号边控制数的新上界

对图G的反符号边控制数进行了研究,给出了一般图的反符号边控制数的若干新上界,并证明这些上界是可达的。

两类冠图的符号罗马控制数

设图G=(V,E)为一个简单无向图,若S?V,则记f(S)=∑v∈sf(v)。若实值函数f:V→{-1,1,2}满足以下两个条件:1) 对于任意的顶点v∈V,均有f(N[v])≥1成立;2) 如果对任意顶点v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V满足f(u)=2,则称该函数为图G的符号罗马控制函数。图G的符号罗马控制数定义为γsR(G)=min{f(V)|f为图G的一个符号罗马控制函数}。本文利用构造法及穷标法主要得到了k-正则图的冠图以及轮图的冠图的符号罗马控制数的精确值。

两类特殊图的符号星控制数

针对“关于图的符号星控制数”一文中有一个定理(关于完全图的符号星控制数)的部分结果是不正确的,文章给出正确的结论及其证明,并确定了k-正则二部图的符号星控制数。

关于图的两类边控制数

引入了图的反符号边全控制的概念.设G=(V,E)是一个图,N(e)表示G中与e相邻的边集,函数f:E→{+1,-1},如果对任意e∈E(G)均有∑f(e′)≤0,其中e′∈N(e),则称f为图G的一个反符号边全控制函数.而γs′t(G)=max∑f(e)|f为G的反符号边全控制函数,e∈E(G)称为图G的反符号边全控制数.分别给出了图的反符号边全控制数和k符号边控制数的一个界限,并确定了轮图的反符号边全控制数和完全偶图Km,n的k-符号边控制数的下界.

pq阶Cayley图的反符号星控制数

设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{-1,1}满足f(E(v))≤0对一切v∈V(G)均成立,则称f为图G的一个反符号星控制函数,图G的反符号星控制数定义为γrss(G)=max{f(E)|f为G的反符号星控制函数}。确定了pq(2<p<q,且p,q为互异的素数)阶群Γ上Cayley图X(Γ,M)的反符号星控制数γrss(X(Γ,M))=-q,M表示群Γ的极小生成集。

关于Cockayne E J等人的一个猜想

Cockayne E J引入了一个图G的k-符号控制数γk-s11(G)的概念,提出了如下猜想:对任意n阶连通图G和正整数k(n2<k≤n),均有γk-s11(G)≤2k-n。我们证明了3方体Q3的5-符号控制数γ-5s11(Q3)=4,从而否定了这个猜想。此外,我们还给出了3-正则二部图k-符号控制数的一个上界,即证明了:对于任意n阶3-正则二部图G和正整数k(n2+1≤k≤n),均有γ-ks11(G)≤2(k+1)-n成立。