两类图的符号全控制数

马梦焓, 红 霞

(洛阳师范学院数学科学学院, 河南洛阳 471022)

1 引言

本文所指定的图均为无向简单图, 文中未说明的符号和术语同文献[1].

设G=(V,E) 是一个图, 其顶点集V=V(G) 和边集E=E(G).对任意u ∈V(G), 则NG(u)为u点在G中的领域,NG[u]=NG(u)∪{u}为u点在G中的闭领域,dG(u)=|NG(v)|为u点在G中的度, 而δ=δ(G) 和∆=∆(G) 分别为图G的最小度和最大度.在不致混淆情况下, 可将NG(v),NG[v],∆(G),δ(G) 分别简单记为N(v),N[v],∆,δ.用Cn,Pn,Fn,Wn分别表示n阶圈、路、扇图和轮图, 其中扇图Fm+1是指m+1 个顶点的图, 即由一个中心顶点w连接m个顶点路Pm的所有顶点的图.轮图Wm+1是指m+1 个顶点的图, 即由一个中心顶点w连接m个顶点圈Cm的所有顶点的图.图n·Fm+1表示把n个扇图的中心点粘接而得到的图, 图n·Wm+1表示把n个轮图的中心点粘接而得到的图.

近几十年来, 图的控制理论的研究内容越来越丰富, 各种类型的符号控制数以及其变化的形式依次被提出, 如图的符号控制数[2−4]、图的边符号控制数[5]、图的边全符号控制数[5]、图的符号全控制数[6]、图的星符号控制数[5]、图的圈符号(边) 控制数[7]、图的团符号(边)控制数[5]、图的逆符号(边) 控制数[5]、图的反符号(边) 控制数[5]、罗曼符号(边) 控制数[8,9]等.其中首次被提出的是图的符号控制概念, 由Dunbar 等人在1995 年提出.图的符号控制数的研究有着广泛的应用背景, 如交通岗位、物资供应点的设置等, 但是符号控制数的计算是NP 完全问题.

目前很多相关学者研究了关于图的符号全控制数的上下界[10,11]以及特殊图的符号全控制数的精确值[12].文献[13]中, 吕新忠等人确定了完全图、星图、扇图、轮图以及完全多部图的符号全控制数.本文中主要得到了两类特殊图n·Fm+1和n·Wm+1的符号全控制数的精确值.特别地, 当n=1 时, 得到了扇图和轮图的符号全控制数, 从而改正了文献[13]中的两个关于扇图和轮图的符号全控制数的结果.

对于图G= (V,E), 定义一个函数f:VR和G的一个子集S ⊆V(G), 记为简单起见, 下文中适合f(u)=+1 的顶点称为+1 点, 适合f(u)=−1 的顶点称为−1 点.

2 基本概念

定义 2.1(文献[6]) 设图G= (V,E) 为一个图, 一个双值函数f:V{1,−1}, 如果对任意的顶点v ∈V, 均有f(N(v))≥1 成立, 则称f为图G的一个符号全控制函数, 图G的符号全控制数定义为γst(G) = min{f(V)|f是图G的一个符号全控制函数}, 并将使得γst(G)=f(V) 的符号全控制函数称f为图G的一个最小符号全控制函数.

从符号全控制的定义, 容易看出以下结论.

引理2.2设函数f是图G的符号全控制函数.对于u ∈V(G), 若d(u)≡0(mod 2), 则f(N(u)) 为偶数.若d(u)≡1(mod 2), 则f(N(u)) 为奇数.

3 主要结果

定理 3.1若n ≥1,m>1, 则

若n ≥1,m=1, 则

证令图n·Fm+1是由n个扇图Fm+1的中心点粘接而得到的图, 记为

首先证明

令f是图n·Fm+1的一个最小符号全控制函数, 则f(V(G))=γst(n·Fm+1).

设图n·Fm+1中所有−1 点个数为t, 所有+1 点个数为s, 则有s+t=nm+1, 从而有

当m=1 时, 图n·Fm+1是n+1 个顶点的星图此时给出星图的符号全控制函数f如下:f(w)=+1,

容易验证, 此时函数f为最优, 从而有

当m=2 时, 图n·Fm+1中每个顶点必标为+1, 从而有γst(n·Fm+1)=2n+1.

下面只考虑当m ≥3.为此通过分三种情况来证明图n·Fm+1的符号全控制数的下界.

情况1当m ≡0(mod 4) 时, 因d(w)≡0(mod 2), 由引理知,f(N(w)) 为偶数, 从而有

情况2当m ≡2(mod 4) 时, 先证明以下五个断言(这里1≤i ≤n).

这与符号全控制函数的定义矛盾.

结合断言1 和断言2, 推出下面的断言3 和断言4.

断言3每条路P(i)上连续三个顶点中至多有两个顶点标为−1.

断言4每条路P(i)上连续四个顶点中至多有两个顶点标为−1.

因为γst(n·Fm+1)=nm+1−2t.由断言 5 可知

情况 3当m ≡1(mod 2) 时, 情况 2 中的断言 1、2、3、4 依然成立.

综上所述, 有

下面给出n·Fm+1的符号全控制的上界.

情况1当m ≡0(mod4) 时, 给出n·Fm+1的一个符号全控制函数f:f(w)=+1.

当m=4 时, 令

当m>4 时, 令

容易验证, 此时f(V)=3, 从而有

情况2当m ≡2(mod 4) 时, 对于1≤i ≤n, 给出n·Fm+1的一个符号全控制函数f:f(w)=+1,

容易验证, 此时f(V)=2n+1, 从而有γst(n·Fm+1)≤2n+1.

情况3当m ≡1(mod 2) 时, 对于1≤i ≤n, 给出n·Fm+1的一个符号全控制函数f:f(w)=+1.

当m=3 时, 令

当m=5 时, 令

当m>5 时, 令

容易验证, 此时f(V)=n+1, 从而有

综上所述, 有

定理1 证毕.

注定理1 中当m= 1 时, 得到了n+1 阶星图的符号全控制数的结果, 这与文[13]中的结论一致.

定理 3.2设n ≥1,m ≥3, 则

证令图n·Wm+1是由n个轮图Wm+1的中心点粘接而得到的图, 记为

令f是图n·Wm+1的一个最小符号全控制函数, 则

设n·Wm+1中所有−1 点个数为t, 所有+1 点个数为s, 则有s+t=nm+1, 从而有

首先证明

若f(w) =−1 时, 注意到, 对于每个点且从而必有故, 有

若f(w)=1 时, 分情况讨论图n·Wm+1的符号全控制数的下界.

情况1当m ≡0(mod 4) 时, 同证明定理1 中的下界时的情况1 一样推导出

情况 2当m ≡2(mod 4) 时, 定理 1 中的断言 1、2、3、4 仍然成立.

断言 7每个圈C(i)上顶点中至多有个标为−1 的点.因为同理, 有

情况 3当m ≡1(mod 2) 时, 定理 1 中的断言 1、2、3、4 仍然成立.

考虑到当f(w)=−1 和f(w)=1 时的图n·Wm+1的符号全控制数的下界, 容易得出

下面再考虑图n·Wm+1的符号全控制的上界.同定理1 的证明, 现只需定义一个符号全控制数函数g使得g=f(这里f是指定理1 情况3 中给出的函数f).

因图n·Wm+1比图n·Fm+1多了边增加此边时只有对两个端点的符号全控制数有变化.事实上, 在符号全控制数函数g下, 有对于顶点有g(N(u))=f(N(u)).容易验证, 得出

证毕.

特别地, 定理1 和定理2 中当n=1 时, 分别得到扇图和轮图的符号全控制数的结果.

推论 3.3若n=1,m ≥1, 则

若n=1,m ≥2, 则

注事实上, 定理1 证明过程中的断言3 否定了文[13]中的证明过程, 从而得出扇图和轮图的符号全控制数的精确值.