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的全符号控制数.     

图的反符号边全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）的顶点集V上定义一个二值函数f=V→{-1,1},使对任何v∈V,f(N[v])≥1,则称f是图G的一个符号控制函数。图的符号控制函数的权重定义为f(V)=∑v∈vf(V),它的最小权重称为图的符号控制数,记为γs(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)是一个没有孤立顶点的图,如果一个函数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的符号星控制函数}。在图的符号星控制概念的基础上,确定了两类特殊图的符号星控制数。     

阶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

     

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的极小生成集.     

两类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:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值.     

C3×Cn的符号边控制数

G是一个非空图,如果存在一个双值函数f∶E(G){1,-1},使得对任意e∈E(G)均有∑e′∈NG[e]f(e′)≥1成立,则称f为图G的一个符号边控制函数,其中NG[e]∶=NG(e)∪{e}为e的闭边邻域。图G的符号边控制数定义为:γs(′G)=m in{∑e∈E(G)f(e)f为图G的一个符号边控制函数}。确定任意给定图的符号边控制数是相当困难的,因而计算某些特殊图的符号边控制数是有价值的,在此给出了卡方积C3×Cn(n≥3)的符号边控制数。     

关于图的符号团控制数

对于一个非空图G=(V,E)和一个函数f:E→{-1,+1},若SE,则记f(S)=∑_e∈Sf(e).若对于G中每个非平凡的团K均满足f(E(K))≥1,则f被称为G的一个符号团控制函数,G的符号团控制数表达为     

关于图的符号边全控制

设γ’st(G)表示图G的符号边全控制数,给出了一般图G和超立方体的符号边全控制数的一个下界和一个上界,计算了等完全二部图的符号边全控制数的精确值。     

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

点赋权图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）。     

P2n的边幻和标号算法及超边幻和标号算法

设L为简单无向图G从V（G） ∪E（G）→{1,2,…,｜V（G） ∪E（G）｜}的一个双射函数,若L满足以下条件：对L所有的边xy∈E（G）,x、y∈ V（G）,都有L（x）＋L（y）＋L（xy）=C,C为常数,则L是图G的边幻和标号,图G是边幻和图;若在此基础上,图G的顶点标号满足：L（V（G））={1,2,…,｜X（G）｜},则L为图G的超边幻和标号,图G是超边幻和图;主要研究一类图P2n的边幻和标号以及超边幻和标号,并给出了相应的证明.     

强全控制边临界图

不含孤立点的图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-临界图的方法.     

图的符号边全控制数

用γ′_st(G)表示图G的符号边全控制数,给出了一般图的符号边全控制数的下界 ,最后确定完全图的符号边全控制数.