关于图的反符号边控制

引入了图的反符号边控制的概念,设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的反符号边控制函数}.在本文中,我们主要给出了图的反符号边控制数的两个上界,并确定了几类特殊图的反符号控制函数.

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

设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的一个符号边控制函数.本文主要研究任意无三角形图的符号边控制数的下界.

关于图的符号边控制数的一些结论

设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_2×C_n的符号边控制数。

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

利用图的控制理论引入新的参数mo来讨论符号边控制数的界限问题,得到图的符号边控制数关于边数m、最大边度Δe和最小边度δe以及参数mo的一些新的下界.

图的符号边控制数

图的符号边控制数有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其精确值有重要意义.本文确定了图F*n+1、H n和P*n的符号边控制数.

关于图的符号边控制数的上界

本文给出了n阶图的符号边控制数的上界,并提出了相关的若干问题和猜想.

两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.

关于图的符号边控制数

设G为一个n阶连通图,△和δ分别为图G的最大度和最小度,给出了图G的符号边控制数的一个下界,即γ',并确定了几类特殊图的符号边控制数.

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

设γ′s(G)表示图G的符号边控制数.本文证明了:对任意n阶图G,均有γ′s(G)≥「4δ-n28」,并探讨了树和完全二部图的符号边控制数.此外,还提出了若干相关问题和猜想.

轮图的符号边控制数

给出了所有轮图的符号边控制数

关于正则图的符号边控制数

本文讨论了正则图的符号边控制数并确定了一般正则图的符号边控制数的上、下界,进而给出了达到下界的必要条件同时构造出达到下界的特殊图.

关于一类图的符号边控制数

设G为给定的图,且δ(G)≥1,用G′表示图G的每个顶点v上增加d(v)-1个悬挂边所得到的图.徐保根给出了图G′的符号边控制数.本文对上述结果做了详细证明,并给出四个例子.

图的符号边控制与减边控制

设G是一个图,γ′s(G)和γ′m(G)分别表示图G的符号边控制数和减边控制数,利用图的边度序列给出了γ′s(G)和γ′m(G)的下限,并通过图G的子图明确了两者的关系,为找出γ′m(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的一个符号边控制函数。全文对图的符号边控制函数进行了研究,得到了图的符号边控制数的若干新的下界。

两类图的符号边控制数

对于任意正整数m和n,用I(Cm)表示在长为m圈Cm的每个顶点处增添1条悬挂边而得到的图,I(d(v)-1)(Kn)表示在完全图Kn的每个顶点v处增添(d(v)-1)条悬挂边而得到的图.本文确定了I(Cm)的符号边控制数为0,I(d(v)-1)(Kn)的符号边控制数为1/2(3n-n2).

C_3×C_n的符号边控制数

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)是一个简单图,对G每一个边e,e的闭邻域N[e]={e′∈E|e′与e邻接}∪{e},一个函数f∶E→{-1,1}称为图G的一个符号边控制函数,若f[e]=∑e′∈N[e]f(e′)≥1对G每一个边e都成立。G的符号边控制数定义为γ′s(G)=min{∑e∈Ef(e)|f是G的一个符号边控制函数}。本文刻画了这一参数为1,2的所有正则图。

图的有效符号边控制数

设G=(V,E)是一个非空图,若函数f:E→{-1,1}对?e∈E(G)均有∑f(e′)=1e′∈N[e],则称f为图G的一个有效符号边控制函数.图G的有效符号边控制数记为rs′e(G),定义为rs′e(G)=min{∑f(e)|f为图Ge∈E(G)的一个有效符号边控制函数}.在本文中,我们给出了一般图的有效符号边控制数存在的必要条件和一个下界,并且证明了图Pm×Cn不存在有效符号边控制函数,最后给出了立方图的有效符号边控制数存在的充要条件.

两类图的逆符号边控制数

研究了图G的逆符号边控制数γ′s(G).利用穷标法及分类讨论法,主要得到了两类图n·C m和n-Cm逆符号边控制数的精确值,从而推广了已知结果.这里Cm表示长为m的圈,n·Cm和n-Cm分别表示恰有一个公共点和有一条公共边的n个圈的拷贝.

两类图的逆符号边控制数

利用穷标法及分类讨论法得到了两类图W^*n+1和F^*n+1的逆符号边控制数的精确值.这里图W^*n+1表示轮图Cn∨K1的圈Cn的每个顶点上增加一条悬挂边而得到的图,图F^*n+1表示扇图Pn∨K1的路Pn的每个顶点上增加一条悬挂边而得到的图.