汪曉馬，葉淼林

(安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽安慶246133)

隨著圖論的快速發(fā)展，涌現(xiàn)出許多重要的結(jié)論和分支。最近，Nikiforov給出了譜半徑和哈密爾頓圖的最小度[1]；Zhou給出了k-連通圖的一些充分條件與哈密爾頓連通圖譜的一些充分條件[2-3]。另外，圖的控制理論是圖論的一個(gè)重要而有趣的分支，圖的控制理論也由原始的點(diǎn)控制逐步向邊控制發(fā)展，徐保根在文獻(xiàn)[4-5]中給出的“圖的符號(hào)星控制”概念就是其中一個(gè)重要的邊控制，本文中“圖的符號(hào)星獨(dú)立數(shù)”概念源于“圖的符號(hào)星控制數(shù)”。

設(shè)G=(V,E)是階數(shù)為n的簡(jiǎn)單圖，圖G的頂點(diǎn)集記為V(G)={v1,v2,…,vn},圖G的邊集記為E(G)={e1,e2,…,en},用e(G)表示圖G的邊的個(gè)數(shù)，即e(G)= ||E(G)，G的頂點(diǎn)v的度d()v是指G中與v關(guān)聯(lián)的邊的數(shù)目，用Δ=Δ(G)和δ=δ(G)分別表示圖G的最大度與最小度。圖G與H的并表示為G?H，即G?H=(V(G?H),E(G?H))。對(duì)于實(shí)數(shù)x，用■■x表示不大于x的最大整數(shù)，■■x表示不小于x的最小整數(shù)。本文中未說明的符號(hào)及術(shù)語與參考文獻(xiàn)[6-7]一致。

下面先給出一些相關(guān)定義、引理及證明。

定義1設(shè)G=(V,E)是一個(gè)圖，如果存在一個(gè)雙值函數(shù)f:E(G)→{-1,1}對(duì)任意v∈V(G)，都有，則稱f是圖G的符號(hào)星獨(dú)立函數(shù)。

定義2稱W(G)=f為圖G的符號(hào)星獨(dú)立函數(shù) }為圖G的符號(hào)星獨(dú)立數(shù)，并稱此時(shí)的符號(hào)星獨(dú)立函數(shù)為G的一個(gè)最大符號(hào)星獨(dú)立函數(shù)。

其中，邊集{e ∈E(G)|f是圖G的符號(hào)星獨(dú)立函數(shù)且f(e)=1}叫做圖G的符號(hào)星獨(dú)立集；邊集{e∈E(G)|f是圖G的最大符號(hào)星獨(dú)立函數(shù)且f(e)=1}叫做圖G的最大符號(hào)星獨(dú)立集。

顯然，任何非空?qǐng)D的符號(hào)星獨(dú)立函數(shù)總是存在的，在每條邊上都取值為-1即可。對(duì)于任何有限圖G，最大符號(hào)星獨(dú)立函數(shù)總是存在的，但不一定唯-一。

規(guī)定：空?qǐng)D的符號(hào)星獨(dú)立數(shù)為0，即W(Kn)=0。由定義可知，圖G的符號(hào)星獨(dú)立數(shù)也可以取正數(shù)、負(fù)數(shù)，例如，W(K2)=1,W(K3)=-1。

引理1設(shè)v是圖G的一個(gè)頂點(diǎn)，f是G的一個(gè)符號(hào)星獨(dú)立函數(shù)，則有

證明由圖G的符號(hào)星獨(dú)立函數(shù)定義直接可得。

引理2(K?nig,Egerváry)[8]設(shè)圖G是一個(gè)二部圖，則G的最大邊獨(dú)立數(shù)等于最小點(diǎn)覆蓋數(shù)。

引理3圖G是一個(gè)二部圖，則G的最大邊獨(dú)立數(shù)至少為

證明設(shè)α′、β分別表示圖G的最大邊獨(dú)立數(shù)與最小點(diǎn)覆蓋數(shù)。因?yàn)閳DG的每個(gè)頂點(diǎn)至多覆蓋Δ(G)條邊，所以β個(gè)頂點(diǎn)至多覆蓋β?Δ(G)條邊，因此β?Δ(G)≥e(G)，即，由引理2，得

引理4[9]完全圖K2n是一個(gè)1-因子和n-1個(gè)哈密爾頓圈的和。

引理5[9]完全圖K2n是一個(gè)1-可因子化的。

下面給出本文的主要結(jié)論及證明。

定理1設(shè)G是任意n階圖，分別用no、ne表示圖G的奇度點(diǎn)個(gè)數(shù)和偶度點(diǎn)個(gè)數(shù)，則有

證明設(shè)f為圖G的最大符號(hào)星獨(dú)立函數(shù)，則

由引理1，得

定理1給出了圖的符號(hào)星獨(dú)立數(shù)的上界。對(duì)于任何一個(gè)圖，偶數(shù)度頂點(diǎn)的個(gè)數(shù)不超過該圖頂點(diǎn)的個(gè)數(shù)。于是，從定理1的結(jié)論，容易得到下面的推論。

推論1設(shè)圖G是n階圖，則有

證明由定理1知，又因?yàn)閚o≤ n，故

事實(shí)上，推論1是定理1的一個(gè)平凡的推論，從這兩者的關(guān)系中，又可以得到如下的結(jié)論：

推論2設(shè)圖G是n階圖，則等式成立的充分必要條件是圖G中度數(shù)為偶數(shù)的點(diǎn)的個(gè)數(shù)為0且

證明（必要性） 設(shè)，由定理1知，于是n ≤ no，因此ne=0，即圖G中度數(shù)為偶數(shù)的點(diǎn)的個(gè)數(shù)為0，并且W(G)=

下面分析圖的符號(hào)星獨(dú)立函數(shù)的概念與圖的匹配集概念之間的關(guān)系。事實(shí)上，只要讓圖的匹配集中邊賦值為1而其他邊賦值為-1，就得到了該圖的一個(gè)符號(hào)星獨(dú)立函數(shù)，由此可以得到圖的符號(hào)星獨(dú)立數(shù)的一個(gè)下界。

定理2對(duì)任意圖G，均有W(G)≥2α′-e(G)，其中α′為圖G最大匹配集中元素個(gè)數(shù)。

證明設(shè)M是圖G的一個(gè)最大匹配集，則有 ||M=α′。令

顯然f是圖G的一個(gè)符號(hào)星獨(dú)立函數(shù)(不一定是最大的符號(hào)星獨(dú)立函數(shù))，故

定理3設(shè)G是一個(gè)二部圖，則

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

推論3設(shè)G是一個(gè)二部圖，若Δ(G)≤2，則W(G)≥0。

定理4設(shè)Cn是階為n的圈，則當(dāng)n為奇數(shù)時(shí)，W(Cn)=-1；當(dāng)n為偶數(shù)時(shí)，W(Cn)=0。

證明當(dāng)n為偶數(shù)時(shí)，給圈Cn每條邊交錯(cuò)的取值-1和1，不難驗(yàn)證，這樣的賦值正好得到Cn的一個(gè)最大符號(hào)星獨(dú)立函數(shù)，并且-1與1的個(gè)數(shù)正好相等，所以W(Cn)=0。當(dāng)n為奇數(shù)時(shí)，用同樣的方法給圈Cn每條邊賦值，必然恰有兩條相鄰的邊都賦值-1，容易證明，這樣的賦值也正好得到Cn的一個(gè)最大符號(hào)星獨(dú)立函數(shù)，并且-1的個(gè)數(shù)比1的個(gè)數(shù)恰好多一個(gè)，因此W(Cn)=-1。

定理5設(shè)圖G為歐拉圖，則有

（1）當(dāng) ||E(G)為奇數(shù)時(shí)，W(Cn)=-1；

（2）當(dāng) ||E(G)為偶數(shù)時(shí)，W(Cn)=0。

證明由歐拉圖的定義以及用定理4的方法在歐拉閉跡的每條邊上賦值，即可得證。

在圖的控制理論中，求解圖的符號(hào)星控制數(shù)是比較困難的。類似地，求解一個(gè)圖的符號(hào)星獨(dú)立數(shù)也是困難的。最后給出完全圖Kn的符號(hào)星獨(dú)立數(shù)。

定理6設(shè)Kn是n(n≥2)階完全圖，則

證明(證法一)（1）當(dāng)n為奇數(shù)時(shí)，Kn的每個(gè)頂點(diǎn)的度數(shù)n-1為偶數(shù)，從而Kn是歐拉圖。下面分兩種情況討論。

(i)當(dāng)n-1為4的倍數(shù)時(shí)，設(shè)n=4k+1（k為正整數(shù)），則為偶數(shù)，由定理5（2）知，W(G)=0。

(ii)當(dāng)n-1不是4的倍數(shù)時(shí)，設(shè)n=4k-1（k為正整數(shù)），則

為奇數(shù)，由定理5（1）知，W(G)=-1。

（2）當(dāng)n為偶數(shù)時(shí)，當(dāng)n=2時(shí)，定理顯然成立。下設(shè)n≥4。

ni爾頓圈Hi的長度n是偶數(shù)。

定義Kn的一個(gè)符號(hào)星獨(dú)立函數(shù)f：當(dāng)e∈F時(shí)，令f(e)=1;在每個(gè)哈密爾頓圈Hi上，交錯(cuò)地取f的值為1和-1，因?yàn)镠i的長度n是偶數(shù)，所以在每個(gè)哈密爾頓圈Hi上1與-1的個(gè)數(shù)相等。顯然，這樣的定義滿足符號(hào)星獨(dú)立函數(shù)的定義。因此

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

（2）當(dāng)n為偶數(shù)時(shí)，當(dāng)n=2時(shí)，定理顯然成立。下設(shè)n≥4。由引理5可知Kn是1-可因子化的，所以可設(shè)圖Kn分解成n-1個(gè)是1-因子Fi(i=1,2,…,n-1)之和。令

顯然，f是圖Kn的一個(gè)符號(hào)星獨(dú)立函數(shù)，所以，再由推論1的結(jié)論得W(Kn)=。

實(shí)際上，從定理6中偶數(shù)階完全圖的符號(hào)星獨(dú)立數(shù)的結(jié)論可知，定理1中n階圖符號(hào)星獨(dú)立數(shù)的上界其實(shí)是上確界。