图的反全符号控制数

设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个下界的图.

两类乘积图的符号控制数

为了把符号控制数γs(G)=min{ω(f)|f是图G的一个符号控制函数}的概念应用到更多的图类中,扩大符号控制数的研究范围。以笛卡尔乘积图为例,通过对笛卡尔乘积图的顶点数进行数学归纳递推、对最小的符号控制函数的函数值进行反证假设,得到了圈图和路图的两类笛卡尔乘积图的符号控制数。研究结果得出:(1)n≥3时,笛卡尔乘积图C_n□P_3的符号控制数为n+2■n/3」;(2)n≥3时,笛卡尔乘积图C_n□C_3的符号控制数为n。

图的符号控制数的下界

设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）的顶点集V上的二值函数f：→｛－1，1｝称为G的符号控制函数当且仅当对有Σv∈N[v]f（v）≥1.f（V）＝Σv∈Vf（v）称为符号控制函数f的权．称rs（G）=min｛f（V）|f为G的一个符号控制函数｝为G的符号控制数．得到了若干图的符号控制数，并对一般的图提出了一个猜想．

偶图符号控制数的下界

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

几类图的强符号控制数

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

关于图的两类强符号控制数的下界

设图G=(V,E)为无孤立点的简单图,且f:V→{-1,1}为G上的一个函数,如果对于任意的顶点v∈V,均有f[v]≥2,则称f是图G的一个强符号控制函数。图G的强符号控制数定义为γss(G)=min{w(f)|f是图G的强符号控制函数}。设k是1≤k≤|V|的正整数,f:V→{-1,1}为图G上的一个函数,如果在图G中至少有k个顶点,使得f[v]≥2,则称f是图G的一个强k-符号控制函数。图G的强k-符号控制数定义为γkss=min{w(f)|f是图强G的k-符号控制函数}。分别得出了强符号控制数及强k-符号控制数的几种形式的下界。

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时得到了扇图的符号控制数,从而推广了已知结果。

两类图的符号控制数

图G的符号控制数γs(G)有着许多重要的应用背景,因而确定其精确值有重要意义.Cm表示m个顶点的圈,n-Cm和n·Cm分别表示恰有一条公共边或一个公共顶点的n个Cm的拷贝.给出了n-Cm和n·Cm的符号控制数.

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

在定义了图的强符号控制函数和强符号控制数的基础上,给出了一些图的强符号控制数的下界.

两类特殊图的符号控制数

图的符号控制理论与局部占优有关,而一般图的符号控制数难以给出具体的计算公式,同时,在图的应用过程中,某些特殊图的使用比较常见,因此,得到这些特殊图的符号控制数是十分必要的.通过对两类特殊图的符号控制数进行研究,给出它们的符号控制数的表达式.