几类图的负对控制数

设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)是一个简单无向图,若实值函数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)的符号罗马控制数的准确值.     

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

设图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)表示.本文决定了一些特定图类的严格强控制数.     

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

设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）的顶点集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→{1,-1},若S?V,则记f(S)=Σ_(v∈s) f(v).如果对任意的顶点v∈V,均有f(N[v])≥1成立,则称f为图G的一个符号控制函数.图G的符号控制数定义为γ_S(G)=min{f(V) f是图G的一个符号控制函数}.联图G=■∨H是空图■的每个顶点都与图H的每个顶点相连接而成的图.本文主要利用讨论图中-1顶点个数的方法得到下界和用标号法得到上界,从而确定两类联图的符号控制数的精确值,即确定了γ_S(■∨Kn)和γ_S(■∨W_(1·n)).     

广义Sierpiński网络的全控制数

设G=(V,E)为一个无孤立点的图.如果一个双值函数f:V→{0,1}对任意点v∈V,均有f(N(v))≥1成立，则称f为图G的一个全控制函数.图G的全控制数定义为γ_t(G)=min{f(V)|f为图G的一个全控制函数}.该文应用数学归纳法和分类讨论法，得到了以路P_m、圈C_m、完全图K_m为基图的广义Sierpiński网络的全控制数.     

关于图的减控制数

图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）的界．     

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

有向图是极大弧连通的充分条件

设D是一个n阶强连通的有向图.D的逆度定义为,R(D)=∑v∈V(D)max{1/(d+(v)),1/(d-(v))},其中,d+(v)与d-(v)是v的出度和入度.证明了,如果R(D)<2+2/(δ(δ+1))+(n-2δ)/((n-δ-2)(n-δ-1)),其中,δ(D)=min{d+(v),d-(v),v∈V(D)},是最小度,那么,D是极大弧连通的.同时,给出了一个二部图的类似结果.     

图的控制数及全控制数的估计

研究了图的控制数及全控制数，对满足一定条件的图给出了图的控制数及全控制数的估计。     

强全控制边临界图

不含孤立点的图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(或有向图D)内的任意两点u和v,u-v测地线是指在u和v之间(或从u到v)的最短路.I(u;v)表示位于u-v测地线上所有点的集合,对于SV(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S.G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数.G的下测地数g-(G)=min狖g(D):D是G的定向图狚,G的上测地数g+(G)=max狖g(D):D是G的定向图狚.对于两个图G和H,u∈V(G)和v∈V(H),在u和v之间加一条边,然后再收缩这条边uv所得的图,记为GuHv.本文主要研究图GuHv的测地数和上(下)测地数.     

关于图的符号团控制数

对于一个非空图G=(V,E)和一个函数f:E→{-1,+1},若SE,则记f(S)=∑_e∈Sf(e).若对于G中每个非平凡的团K均满足f(E(K))≥1,则f被称为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）。     

关于Scrambling指数的最新研究结果

设 n,q,s是正整数, 满足1≤s相似文献