特殊3-正则图的符号控制函数

对于顶点数为n的3-正则图G,当 v∈V(G),N(N[v])≤t时,则有G的上符号控制函数Γs(G)≤t+2t+4n (0≤t≤6)。

图的全符号控制函数

定义了图的全符号控制函数及其全符号控制数,并得到了若干图的全符号控制数的界.

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

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

关于图的符号控制函数的若干结果

定义在图Ｇ＝（Ｖ，Ｅ）顶点集Ｖ上的一个二值函数ｆ：Ｖ→｛＋１，－１｝，若ｖ∈Ｖ，ｆ（Ｎ［ｖ］）≥１，称ｆ是Ｇ的一个符号控制函数．图Ｇ的符号控制函数ｆ的权重ｆ（Ｖ）＝∑ｖ∈Ｖｆ（ｖ）的最小值定义为图Ｇ的符号控制数，记为γｓ（Ｇ）．本文给出了图的最小控制函数的几个性质定理．

图的反全符号控制数

设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的反全符号控制数。

图的圈符号控制数

设G=(V,E)是一个图,一个函数f:V→{-1,1}如果满足∑v∈V(C)f(v)≥1对G中每一个导出圈C均成立,则称f为图G的一个圈符号控制函数,图G的圈符号控制数定义为γsc(G)=min{∑v∈V(G)f(v):f为图G的一个圈符号控制函数}。得到了图的圈符号控制数的若干下界,并刻划了满足δ≥2且γsc(G)=4-V(G)的所有图。

关于图的弱符号控制数的下界

图G的弱符号控制数γws(G)有着许多重要的应用背景,因而确定其下界有重要意义.在构造适当点集的基础上,给出了图的弱符号控制数的4个独立的下界,并给出了达到这4个下界的图.

图的符号控制数的下界

设G是一个图,一个函数f:V→{-1,+1}如果Σv∈N[u]f(v)≥1对于每个点u∈V成立,则称f为图G=(V,E)的一个符号控制函数。一个图G的符号控制数定义为γs(G)=min{Σv∈V(G)f(v)|f为图G的符号控制函数}。该文主要给出了一个图G的符号控制数γs(G)的若干新下限,并刻划了满足γs(G)=|V(G)|的所有图G。

特殊图类的符号控制数

图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值.

关于Double图的符号控制数

图的符号控制数在现实生活中有许多应用背景,但图的符号控制数的计算是NP完全问题.给出了一般图G的Double图的符号控制数下界,确定了圈和路的Double图的符号控制数.

无三角形图的符号边控制数下界

设G=(V,E)是一个顶点数为n的图,给定一个边权重函数f:E→{+1,-1}.如果对于任意一条边e∈E,都满足所有与边e有公共端点的边e^(*)(包括边e)的权重f(e^(*))的和大于或等于1,那么我们称这个函数f是图G的一个符号边控制函数.图G的符号边控制数定义为γ′s(G)=min{Σe∈Ef(e)},其中f是G的一个符号边控制函数.本文主要研究任意无三角形图的符号边控制数的下界.

几种图的弱符号控制数

本文对弱符号控制函数和弱符号控制数的性质进行了研究,在此基础上,得出完全图、完全二部图、圈、路等的弱符号控制数的性质。

一类偶图的符号边控制数

对于任意正整数m和n,构造了一类偶图(二部图)G(m,n),其阶为2mn,边数为3mn-m-n,确定了其符号边控制数为γ′s(G(m,n))=m+n-mn.从而证明了n阶偶图的最小符号边控制数B(n)<1+22n-n2,并指出了文[6]一个猜想的错误.

偶图符号控制数的下界

设G=(V,E)是一个图,一个实值函数f:V→{-1,+1}满足∑v∈N[u]f(v)≥1对一切u∈V(G)都成立,则称f为图G的一个符号控制函数。图G的符号控制数定义为γs(G)=min{∑v∈V(G)f(v)|f为图G的符号控制函数}。研究了偶图的符号控制问题,主要给出了偶图符号控制数的两个下界。

一些特殊图的符号控制数

给出了荷兰m-风车图、法国m-风车图以及P_n^2符号控制数的确切值.

n·C_3的全符号控制数

设γ*s(G)表示图G的全符号控制数,Cm表示m个点的圈,n·Cm表示恰有一个公共顶点的n个Cm的拷贝.本文给出了n·C3的全符号控制数.

几类图的强符号控制数

本文对几类特殊图的强符号控制函数及强符号控制数进行了研究,给出了完全图、完全二部图、路及圈的强符号控制数。

C_n^2图的符号控制数

设图G=G(V,E),令函数f:V→{-1,1},f的权w(f)=∑v∈Vf[v],对v∈V,定义f[v]=∑u∈N[v]f(u),这里N[v]表示V中顶点v及其邻点的集合。图G的符号控制函数为f:V→{-1,1}满足对所有的v∈V有f[v]≥1,图G的符号控制数γs(G)就是图G上符号控制数的最小权,称其f为图G的γs-函数。研究了C2n图,通过给出它的一个γs-函数得到了其符号控制数。

n·P_m的符号控制数

图G的符号控制数γs(G)有着许多重要的应用背景,因而确定其精确值有重要意义.Pm表示长为m的路,n Pm分别表示恰有一个公共顶点的n个Pm的拷贝.本文给出了n Pm的符号控制数.

一类联图的符号控制数

设图G=(V,E)为一个图,一个双值函数f:V→{1,-1},若SV,则记f(S)=∑v∈Sf(v)。如果对任意的顶点v∈V,均有f(N[v])≥1成立,则称f为图G的一个符号控制函数,图的符号控制数定义为γs(G)=min{f(V)|f是图G的一个符号控制函数}图G=Km∨Pn表示图Km的每个顶点与路Pn的每个顶点相连接的联图。本文主要用分类讨论法和穷标法得到了图G的符号控制数的精确值,即确定了γs(Km∨Pn)。特别地,此联图中当m=1时得到了扇图的符号控制数,从而推广了已知结果。