圖的逆符號邊全控制的性質(zhì)

黃中升

（廊坊師范學院 數(shù)信學院，河北 廊坊 065000）

圖的逆符號邊全控制的性質(zhì)

黃中升

（廊坊師范學院 數(shù)信學院，河北 廊坊 065000）

本文將圖的符號邊全控制引申為圖的逆符號邊全控制，并在此基礎上研究圖的逆符號邊全控制數(shù)的性質(zhì).

圖；逆符號邊全控制函數(shù)；逆符號邊全控制數(shù)

1 引言

本文所指的圖均為無向簡單圖，文中未說明的符號和術語同于文獻[1].

近年來，圖的控制概念得到延伸和推廣[2-3]，2006年徐寶根教授定義了符號邊全控制[4].本文將圖的符號邊全控制引申為圖的逆符號邊全控制，并在此基礎上研究圖的逆符號邊全控制數(shù)的性質(zhì).

定義1[4]設G=(V,E)為一個非空圖，一個函數(shù)f:E→{-1,1}，如果對每一條邊 e∈E，均有 f(N(e))≥1成立，則稱f為圖G的一個符號邊全控制函數(shù)，圖G的符號邊全控制數(shù)γ'st(G)=min{f(E)|f為圖G的符號邊控制函數(shù)}.

下面引入圖的逆符號邊全控制的概念.

定義2 設G=(V,E)為一個非空圖，對于圖G的一個函數(shù)f:E→{-1,1}，如果對任意e∈E(G)，均有f(N(e))≤1成立，則稱f為圖G的一個逆符號邊全控制函數(shù)，圖G的逆符號邊全控制數(shù)為γ'st(G)=max{f(E)|f為圖G的逆符號邊全控制函數(shù)}.對于圖G的一個逆符號邊全控制函數(shù)f，如果不存在圖G的逆符號邊全控制函數(shù)g(f≠g)，使得對于任意的e∈E，均有g(e)≥f(e)，則稱f是G的一個極大逆符號邊全控制函數(shù).如果圖G的一個逆符號邊全控制函數(shù)f的權重 f(E)=γ'st(G)，則稱 f是圖 G 的一個 γ'st(G)函數(shù).特別地，補充定義 γ'st(K1)=γ'st(K2)=0.

利用定義2能夠解決圖論中關于邊集的一個劃分問題：如果將一個給定圖G的邊集E劃分為E1和E2兩類，使得G的每條邊的邊鄰域中第一類邊至多比第二類邊多一條，那么兩類邊的數(shù)目之差|E1|-|E2|的最大值就是這個圖的逆符號邊全控制數(shù).

2 主要結果

定理1 對任意非空簡單圖G，均有γ'st(G)≡|E(G)|(mod2)

證明 設f是圖G的一個γ'st函數(shù)，令P={e∈E|f(e)=1}，M={e∈E|f(e)=-1}，則 |E(G)|=|P|+|M|.

當|E(G)|為奇數(shù)時，令|E(G)|=2k+1,則|P|+|M|=2k+1，γ'st(G)=|P|-|M|=|P|-(2k+1-|P|)=2|P|-2k-1為奇數(shù)；當|E(G)|為偶數(shù)時,令|E(G)|=2k,則|P|+|M|=2k,γ'st(G)+|P|-|M|=|P|-(2k-|P|)=2(|P|-k)為偶數(shù).從而有 γ'st(G)≡|E(G)|(mod2)．

定理2 對任意兩個不交的圖G1和G2，均有

由定義顯然可得.

定理3 設f為圖G的一個逆符號邊全控制函數(shù)，則f為圖G的一個極大的逆符號邊全控制函數(shù)當且僅當對于滿足f(e)=-1的任意一條邊e∈E，都存在邊e0∈N(e),使得f(N(e0))∈{0,1}.

充分性 若f不是極大的逆符號邊全控制函數(shù)，則存在一個極大的逆符號邊全控制函數(shù)g，使得g>f,即對任意e∈E，有g(e)≥f(e)，且至少存在一條邊 e'∈E，有 g(e')>f(e')成立.因而有 f(e')=-1，g(e')=1.由假設可知存在一條邊e0∈N(e'),使得f(N(e0))∈{0,1}，但由于對任意 e∈N(e'))，有 g(e)≥f(e)，且 g(e')=f(e')+2，我們有 g(N(e0))=f(N(e0))+2≥2，與 g為逆符號邊全控制函數(shù)相矛盾.證畢.

定理4 對于任意非空圖G,均有γ'st(G)+γ'st(G)≥2,并且此下界是最好可能的.

證明 設f為G的一個權重最小的符號邊全控制函數(shù),則γ'st(G)=f(E).令g=-f,則對于任意e∈E,有g(N(e))=-f(N(e))≤-1,由定義2和定理3可知,g是G的一個逆符號邊全控制函數(shù),但不是G的一個極大逆符號.從而 γ'st(G)>g(E)=-f(E)=-γ'st(G),故 γ'st(G)+γ'st(G)>0.由于 γ'st(G)和 γ'st(G)具有相同的奇偶性,因此 γ'st(G)+γ'st(G)≥2.

對于2n階星圖K1,2n-1,由定義1和定義2易知,γ'st(K1,2n-1)=-1，γ'st(K1,2n-1)=3,從而 γ'st(K1,2n-1)+γ'st(K1,2n-1)=2,因此定理給出的下界是最好可能的.證畢.

這樣，定理4給出了圖G的逆符號邊全控制數(shù)和符號邊全控制數(shù)的關系.

〔1〕Bondy J A,Murty V S R.Graph Theory with Applications[M],Elsevier,Amsterdam,1976.

〔2〕Haynes T W,Hedetniemi S T,Slater P J,Fundamentals ofDominationinGraphs[M].New York,1998.

〔3〕Haynes T W,Hedetniemi S T,Slater P J,Domination in Graphs[M].New York,1998.

〔4〕徐寶根.關于圖的符號邊全控制[J].華東交通大學學報,2006,23(2):129-131.

O157.5

A

1673-260X（2010）06-0010-02

河北省教育廳2009年自然科學研究計劃（2009331）;河北省自然科學基金(A2008000128);廊坊師范學院青年項目（LSZQ200225）; 廊坊師范學院科學研究項目（LSZY200901）