章芳芳，葉淼林

（安慶師范大學(xué)數(shù)理學(xué)院，安徽安慶246133）

設(shè)圖G= (V,E),|V|=n，定義在V上的一個(gè)雙值函數(shù)f:V→{ - 1,1 }，如果滿(mǎn)足條件：V中至少一半的頂點(diǎn)v使得

成立，這里N[v]=N(v)?{v}，則稱(chēng)f為圖G的一個(gè)主控制函數(shù)[1-2]。圖G的主控制數(shù)[1-2]定義為

文獻(xiàn)[3-7]給出了圖的主控制數(shù)的一些結(jié)果，本文提出圖的主獨(dú)立數(shù)的概念：

設(shè)G=(V,E)為一個(gè)圖，一個(gè)雙值函數(shù)f:V→{ - 1,1 }，如果滿(mǎn)足條件V中至少一半的頂點(diǎn)v使得f[v]≤1 成 立 ，則 稱(chēng)f為 圖G的 一 個(gè) 主 獨(dú) 立 函 數(shù) 。 圖G的 主 獨(dú) 立 數(shù) 定 義 為αmaj(G)=為圖G的一個(gè)主獨(dú)立函數(shù)且f(V)=下面討論主獨(dú)立數(shù)的性質(zhì)和下界。

定理1對(duì)于任意的n階連通圖G，均有

證明（1）當(dāng)n=2l+1 為奇數(shù)時(shí)，將V劃分成兩個(gè)部分：V(G)=V1?V2，且V1?V2=φ, |V1|=l, |V2|=l+1且使 |E(V1,V2) |盡可能大(這里E(V1,V2)表示一端點(diǎn)在V1中，另一端點(diǎn)在V2中的所有邊構(gòu)成的集合)。定義圖G的一個(gè)主獨(dú)立函數(shù)f

當(dāng)u∈V2時(shí)，有否則將此點(diǎn)u移至V1中，使得新的更大，這與拆分要求中的 |E(V1,V2) |盡可能大相矛盾，故有f[u]≤1，所以f為圖G的一個(gè)主獨(dú)立函數(shù)，而

故αmaj(G)≥f(V)=1。

（2）當(dāng)n=2l+2為偶數(shù)時(shí)，取u∈V(G)使得2l+1階圖G-u為連通圖。

由（1）知，存在一個(gè)主獨(dú)立函數(shù)f1，使得f1(V(G-u))=1。擴(kuò)充f1到f定義f(u)=-1，則f為圖G的一個(gè)主獨(dú)立函數(shù)，且f(V)=f1(V(G-u))+f(u)=1+(-1)=0。故αmaj(G)≥f(V)=0，綜上所述，定理1成立。

推論1若n≥2為整數(shù)時(shí)，有

證明由主獨(dú)立數(shù)的定義和任意完全圖各點(diǎn)地位相同即知。

推論2當(dāng)n≥2為整數(shù)時(shí)，有αmaj(K1,n)=n-1。

證明由圖K1,n的特征，分拆V(G)=V1?V2，其中 |V1|=1, |V2|=n。定義K1,n的主獨(dú)立函數(shù)f：當(dāng)v∈V1時(shí)，f(v)=-1；當(dāng)v∈V2時(shí),f(v)=1。故f為K1,n的一個(gè)主獨(dú)立函數(shù)，且此時(shí)f(V)的值是最大的，故

推論3當(dāng)n≥m≥ 2均為整數(shù)時(shí)，有

證明令G=(V,E)且G?Km,n，其中n≥m≥ 2 為整數(shù)，且U和W為G的二部劃分頂點(diǎn)集，且 |U|=m,|W|=n。令f為G上的最大主獨(dú)立函數(shù)，且在f下給W中盡可能多的頂點(diǎn)標(biāo)號(hào)為+1。令U+和U-為U的頂點(diǎn)集，他們的頂點(diǎn)在f下的標(biāo)號(hào)分別為+1和 -1。W+和W-也類(lèi)似定義，則

當(dāng)m=n時(shí)，W中至少有一個(gè)頂點(diǎn)w使得f(N[w])≤ 1 成立，如果需要，可重新定義U和W；當(dāng)m＜n時(shí)，因?yàn)閂中的頂點(diǎn)在f下至少一半的閉包和小于等于1，知道W中至少一個(gè)頂點(diǎn)w有f(N[w])≤ 1 成立。對(duì)這樣一個(gè)頂點(diǎn)w，有f(w)+f(U)=f(N[w])≤ 1，故f(U)≤1-f(w)≤2。

現(xiàn)證明W=W+，即證W中每個(gè)頂點(diǎn)在f下均被標(biāo)號(hào)為+1。假設(shè)有W-≠?，若U=U-，則令g:V→{ - 1,1 }為一個(gè)雙值函數(shù)，定義

則g(N[w])=g(U)+g(w)=1-m≤ 1 對(duì)每個(gè)w∈W成立。因?yàn)閚≥m，即 |W|≥ |U|,可得g是值大于f的一個(gè)主獨(dú)立函數(shù)，這與f的定義矛盾，故至少存在一個(gè)頂點(diǎn)u在U+中?，F(xiàn)令h是V→ { - 1.1 }的一個(gè)雙值函數(shù)，定義因f(U)≤2，故h(U)=f(U)-2 ≤ 0，所以h(N[w])=h(U)+h(w)≤0+1≤1。因?yàn)閚≥m，即|W|≥ |U|,可得，h是G上的一個(gè)主獨(dú)立函數(shù)，h下W中標(biāo)號(hào)為+1的頂點(diǎn)數(shù)比f(wàn)在W中標(biāo)號(hào)+1的頂點(diǎn)數(shù)多，這與f的定義矛盾，所以W=W+?，F(xiàn)令f(N[w])≤ 1,其中w∈W,則f(U)+f(w)=f(N[w])≤1。即f(U)≤1-f(w),故|U+|-|U-|=f(U)≤1-f(w)=0，所以|U+|≤|U-|。又m=|U+|+|U-|，可得所以。進(jìn)一步，對(duì)V中的個(gè)頂點(diǎn)在f下的標(biāo)號(hào)均為-1，剩下的個(gè)頂點(diǎn)在f下的標(biāo)號(hào)均為+1，于是可得到G上一個(gè)值為的一個(gè)主獨(dú)立函數(shù)。因此有

推論4對(duì)任一正整數(shù)k，則存在一個(gè)完全二部圖G使得αmaj(G)≥k。

推論5對(duì)任意n階r正則圖且G(r≥ 2)，均有。

證明令G是一個(gè)n個(gè)頂點(diǎn)的r正則圖且G=(V,E)，假設(shè)f是V上的一個(gè)主獨(dú)立函數(shù)，且

令V-記為V中的滿(mǎn)足f(N[v])≤ 1的頂點(diǎn)集，則因此有

又因?yàn)楫?dāng)v∈V-時(shí)，f(N[v])≤ 1；當(dāng)v∈V+時(shí)，f(N[v])≤r+1，故

定理2當(dāng)m≥0為整數(shù)時(shí)，令P(m,αmaj)表示主獨(dú)立數(shù)為m的連通圖的最小階數(shù)，則有

證明令G=(V,E)是一連通圖，且αmaj=m。現(xiàn)在考慮G上的一個(gè)最大的主獨(dú)立函數(shù)f,又令P和M是G的頂點(diǎn)集，即G=P?M，且有

則m=f(V)= |P|-|M|。故 |M|= |P|-m,且 |P|=|M|+m，則有 |M|≥ 1，否則對(duì)G上的每個(gè)頂點(diǎn)v有f[N(v) ]≥2，這與f是G上的一個(gè)主獨(dú)立函數(shù)矛盾，因此有 |V|= |P|+|M|=|M|+m+|M|=2 |M|+m≥m+2，并且這個(gè)下界是可以取到的，如K2,m，它是階為m+2的連通圖，且主獨(dú)立數(shù)為m，綜上所述有P (m,αmaj)=m+2。

定理3令為n階圖且。

證明由推論3可知下面證明。

設(shè)f是圖G的一個(gè)主獨(dú)立函數(shù)，且使得αmaj(G)=f(V)，由主獨(dú)立函數(shù)的定義知，V中至少有一個(gè)頂點(diǎn)v，使得注意到從而V中至少有個(gè)頂點(diǎn)在f下的標(biāo)號(hào)為-1，即V中至多有個(gè)頂點(diǎn)在f下的標(biāo)號(hào)為+1，故有

圖的主獨(dú)立數(shù)是圖的一個(gè)新的分支，本文主要給出了圖的主獨(dú)立數(shù)的概念和一些相關(guān)的性質(zhì)特征，但是還有新的問(wèn)題需要去研究，這里就不一一闡述了。