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

黃中升

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

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

黃中升

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

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

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

1 引言

本文所指的圖均為無向簡(jiǎn)單圖，文中未說明的符號(hào)和術(shù)語同于文獻(xiàn)[1].

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

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

下面引入圖的逆符號(hào)邊全控制的概念.

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

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

2 主要結(jié)果

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

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

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

定理2 對(duì)任意兩個(gè)不交的圖G1和G2，均有

由定義顯然可得.

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

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

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

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

對(duì)于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的逆符號(hào)邊全控制數(shù)和符號(hào)邊全控制數(shù)的關(guān)系.

〔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〕徐寶根.關(guān)于圖的符號(hào)邊全控制[J].華東交通大學(xué)學(xué)報(bào),2006,23(2):129-131.

O157.5

A

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

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