图的符号星独立数

汪晓马，叶淼林

(安庆师范大学数学与计算科学学院，安徽安庆246133)

随着图论的快速发展，涌现出许多重要的结论和分支。最近，Nikiforov给出了谱半径和哈密尔顿图的最小度[1]；Zhou给出了k-连通图的一些充分条件与哈密尔顿连通图谱的一些充分条件[2-3]。另外，图的控制理论是图论的一个重要而有趣的分支，图的控制理论也由原始的点控制逐步向边控制发展，徐保根在文献[4-5]中给出的“图的符号星控制”概念就是其中一个重要的边控制，本文中“图的符号星独立数”概念源于“图的符号星控制数”。

设G=(V,E)是阶数为n的简单图，图G的顶点集记为V(G)={v1,v2,…,vn},图G的边集记为E(G)={e1,e2,…,en},用e(G)表示图G的边的个数，即e(G)= ||E(G)，G的顶点v的度d()v是指G中与v关联的边的数目，用Δ=Δ(G)和δ=δ(G)分别表示图G的最大度与最小度。图G与H的并表示为G⋃H，即G⋃H=(V(G⋃H),E(G⋃H))。对于实数x，用■■x表示不大于x的最大整数，■■x表示不小于x的最小整数。本文中未说明的符号及术语与参考文献[6-7]一致。

下面先给出一些相关定义、引理及证明。

定义1设G=(V,E)是一个图，如果存在一个双值函数f:E(G)→{-1,1}对任意v∈V(G)，都有，则称f是图G的符号星独立函数。

定义2称W(G)=f为图G的符号星独立函数 }为图G的符号星独立数，并称此时的符号星独立函数为G的一个最大符号星独立函数。

其中，边集{e ∈E(G)|f是图G的符号星独立函数且f(e)=1}叫做图G的符号星独立集；边集{e∈E(G)|f是图G的最大符号星独立函数且f(e)=1}叫做图G的最大符号星独立集。

显然，任何非空图的符号星独立函数总是存在的，在每条边上都取值为-1即可。对于任何有限图G，最大符号星独立函数总是存在的，但不一定唯-一。

规定：空图的符号星独立数为0，即W(Kn)=0。由定义可知，图G的符号星独立数也可以取正数、负数，例如，W(K2)=1,W(K3)=-1。

引理1设v是图G的一个顶点，f是G的一个符号星独立函数，则有

证明由图G的符号星独立函数定义直接可得。

引理2(König,Egerváry)[8]设图G是一个二部图，则G的最大边独立数等于最小点覆盖数。

引理3图G是一个二部图，则G的最大边独立数至少为

证明设α′、β分别表示图G的最大边独立数与最小点覆盖数。因为图G的每个顶点至多覆盖Δ(G)条边，所以β个顶点至多覆盖β⋅Δ(G)条边，因此β⋅Δ(G)≥e(G)，即，由引理2，得

引理4[9]完全图K2n是一个1-因子和n-1个哈密尔顿圈的和。

引理5[9]完全图K2n是一个1-可因子化的。

下面给出本文的主要结论及证明。

定理1设G是任意n阶图，分别用no、ne表示图G的奇度点个数和偶度点个数，则有

证明设f为图G的最大符号星独立函数，则

由引理1，得

定理1给出了图的符号星独立数的上界。对于任何一个图，偶数度顶点的个数不超过该图顶点的个数。于是，从定理1的结论，容易得到下面的推论。

推论1设图G是n阶图，则有

证明由定理1知，又因为no≤ n，故

事实上，推论1是定理1的一个平凡的推论，从这两者的关系中，又可以得到如下的结论：

推论2设图G是n阶图，则等式成立的充分必要条件是图G中度数为偶数的点的个数为0且

证明（必要性） 设，由定理1知，于是n ≤ no，因此ne=0，即图G中度数为偶数的点的个数为0，并且W(G)=

下面分析图的符号星独立函数的概念与图的匹配集概念之间的关系。事实上，只要让图的匹配集中边赋值为1而其他边赋值为-1，就得到了该图的一个符号星独立函数，由此可以得到图的符号星独立数的一个下界。

定理2对任意图G，均有W(G)≥2α′-e(G)，其中α′为图G最大匹配集中元素个数。

证明设M是图G的一个最大匹配集，则有 ||M=α′。令

显然f是图G的一个符号星独立函数(不一定是最大的符号星独立函数)，故

定理3设G是一个二部图，则

证明由定理2与引理3可得W(G)≥2α′-e(G)≥

推论3设G是一个二部图，若Δ(G)≤2，则W(G)≥0。

定理4设Cn是阶为n的圈，则当n为奇数时，W(Cn)=-1；当n为偶数时，W(Cn)=0。

证明当n为偶数时，给圈Cn每条边交错的取值-1和1，不难验证，这样的赋值正好得到Cn的一个最大符号星独立函数，并且-1与1的个数正好相等，所以W(Cn)=0。当n为奇数时，用同样的方法给圈Cn每条边赋值，必然恰有两条相邻的边都赋值-1，容易证明，这样的赋值也正好得到Cn的一个最大符号星独立函数，并且-1的个数比1的个数恰好多一个，因此W(Cn)=-1。

定理5设图G为欧拉图，则有

（1）当 ||E(G)为奇数时，W(Cn)=-1；

（2）当 ||E(G)为偶数时，W(Cn)=0。

证明由欧拉图的定义以及用定理4的方法在欧拉闭迹的每条边上赋值，即可得证。

在图的控制理论中，求解图的符号星控制数是比较困难的。类似地，求解一个图的符号星独立数也是困难的。最后给出完全图Kn的符号星独立数。

定理6设Kn是n(n≥2)阶完全图，则

证明(证法一)（1）当n为奇数时，Kn的每个顶点的度数n-1为偶数，从而Kn是欧拉图。下面分两种情况讨论。

(i)当n-1为4的倍数时，设n=4k+1（k为正整数），则为偶数，由定理5（2）知，W(G)=0。

(ii)当n-1不是4的倍数时，设n=4k-1（k为正整数），则

为奇数，由定理5（1）知，W(G)=-1。

（2）当n为偶数时，当n=2时，定理显然成立。下设n≥4。

ni尔顿圈Hi的长度n是偶数。

定义Kn的一个符号星独立函数f：当e∈F时，令f(e)=1;在每个哈密尔顿圈Hi上，交错地取f的值为1和-1，因为Hi的长度n是偶数，所以在每个哈密尔顿圈Hi上1与-1的个数相等。显然，这样的定义满足符号星独立函数的定义。因此

(证法二)（1）同证法一。

（2）当n为偶数时，当n=2时，定理显然成立。下设n≥4。由引理5可知Kn是1-可因子化的，所以可设图Kn分解成n-1个是1-因子Fi(i=1,2,…,n-1)之和。令

显然，f是图Kn的一个符号星独立函数，所以，再由推论1的结论得W(Kn)=。

实际上，从定理6中偶数阶完全图的符号星独立数的结论可知，定理1中n阶图符号星独立数的上界其实是上确界。