徐保根，康洪波，趙利芬，操葉龍

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西 南昌 331013)

本文中所指的圖均為無(wú)向簡(jiǎn)單圖,文中未說(shuō)明的符號(hào)和術(shù)語(yǔ)同于文獻(xiàn)[1]。

近幾年來(lái)，圖的控制理論研究的內(nèi)容越來(lái)越廣泛，各類(lèi)控制概念相繼產(chǎn)生且研究成果不斷豐富,Haynes等[2]綜述了近幾些年來(lái)圖的控制理論研究方面的主要研究成果。文獻(xiàn)[3]首先提出了圖的符號(hào)邊控制概念，獲得了符號(hào)邊控制數(shù)的許多界限，并將這一概念推廣到邊上的多種符號(hào)控制，如符號(hào)星控制[4]、符號(hào)圈控制[5]、符號(hào)團(tuán)控制[6]等等。同樣地，這也產(chǎn)生了對(duì)應(yīng)的減邊控制概念，從而使得控制理論研究?jī)?nèi)容和研究成果越來(lái)越豐富，文獻(xiàn)[7] 綜述了這些研究成果。

1 若干定義

設(shè)G=(V,E)是一個(gè)圖，若C為圖G中的一個(gè)圈，若V(C)在G中的導(dǎo)出子圖G[V(C)]=C。則稱(chēng)C為圖G的一個(gè)導(dǎo)出圈或無(wú)弦圈。

文獻(xiàn)[8]中首先提出并研究了圖的圈符號(hào)控制。

定義1[8]設(shè)G=(V,E)是一個(gè)圖，一個(gè)函數(shù)f:V→{-1,1}如果滿(mǎn)足f(V(C))≥1對(duì)G中每一個(gè)導(dǎo)出圈C均成立，則稱(chēng)f為圖G的一個(gè)圈符號(hào)控制函數(shù)，圖G的圈符號(hào)控制數(shù)定義為γsc(G)=min{f(V):f為圖G的一個(gè)圈符號(hào)控制函數(shù)}。

2 主要結(jié)論及其證明

首先給出滿(mǎn)足δ≥2且γsc(G)=4-V(G)的圖G的一個(gè)刻劃。

證明由于δ≥2，圖G至少有一個(gè)圈，從而對(duì)圖G的每一個(gè)圈符號(hào)控制函數(shù)f，G中至少有兩個(gè)點(diǎn)v∈V(G)滿(mǎn)足f(v)=1，故γsc(G)≥4-n。

充分性是顯然的。下面證明必要性。

A={v∈V(G)f(v)=1},

B={v∈V(G)f(v)=-1},

γsc(G)=A-B=2A-n

故A=2，記A={u,v}。

論斷1G的邊連通度λ(G)≥2。

若G為不連通圖，即G至少有兩個(gè)分支，由于δ≥2，G的每個(gè)分支中至少有一個(gè)導(dǎo)出圈，從而至少有一個(gè)導(dǎo)出圈C，使C上至多有A中一個(gè)點(diǎn)，故f(V(C))≤-1，矛盾。

若G中有割邊e=ab∈E(G)，令G1=G-e，G1至少有兩個(gè)分支，由于δ(G)≥2，a點(diǎn)所在的分支Ga中至多有一個(gè)1度點(diǎn)(a點(diǎn))，其它點(diǎn)的度至少為2，故Ga中有導(dǎo)出圈。同理，Gb中也有導(dǎo)出圈，從而至少有一個(gè)導(dǎo)出圈C，使C上至多有A中一個(gè)點(diǎn)，故f(V(C))≤-1，矛盾。因此，論斷1成立。

由于λ(G)≥2，故G中任何點(diǎn)都在一個(gè)導(dǎo)出圈中，由A=2知，G中任何導(dǎo)出圈均為一個(gè)三角形，且均包含u和v兩點(diǎn)(否則，存在導(dǎo)出圈C，f(V(C))≤0，矛盾)。因此，uv∈E(G)。

由于e邊的兩端點(diǎn)均不在A中，故f(V(C))≤0，矛盾。因此，論斷2成立。

給出圖的圈符號(hào)控制數(shù)的一個(gè)下界。

定理2 對(duì)于任意n階圖G，若其最小度δ=δ(G)≥2，則有

γsc(G)≥2δ-n

并且此下界是最好可能的。

A={v∈V(G)f(v)=1},

B={v∈V(G)f(v)=-1}

記A=s，B=t，由定義知，

γsc(G)=s-t=2s-n

下面說(shuō)明此下界是最好可能的。

對(duì)于一個(gè)無(wú)圈圖G，我們知道γsc(G)=-V(G)，這使得對(duì)于無(wú)圈圖來(lái)說(shuō)，圖的圈符號(hào)控制數(shù)是已知的，無(wú)需研究。下面針對(duì)有圈圖給出圈符號(hào)控制數(shù)的一個(gè)下界。

定理3 對(duì)于任意n階圖G，E(G)=m，若G中至少有一個(gè)圈，則有

A={v∈V(G)f(v)=1},

B={v∈V(G)f(v)=-1}

記A=s，B=t，由定義知，

γsc(G)=s-t=2s-n

m=E(G[A])+E(A,B)+E(G[B])≤

參考文獻(xiàn)：

[1] BONDY J A, MURTY U S R.圖論及其應(yīng)用 [M]. 吳望名,等譯. 北京：科學(xué)出版社，1984.

[2] HAYNES T W, HEDETNIEMI S T, SLATER P J. Domination in graphs [M]. New York:Marcel Dekker Inc, 1998.

[3] XU B G. On signed edge domination numbers of graphs [J]. Discrete Math, 2001, 239: 179-189.

[4] XU B G. Two classes of edge domination in graphs [J]. Discrete Appl Math, 2006, 154: 1541-1546.

[5] XU B G. On signed cycle domination numbers in graphs [J]. Discrete Math, 2009, 309: 1007-1012.

[6] 徐保根. 關(guān)于圖的團(tuán)符號(hào)控制數(shù)[J].系統(tǒng)科學(xué)與數(shù)學(xué), 2008, 3: 282-287.

[7] 徐保根. 圖的控制理論[M]. 北京：科學(xué)出版社，2008.

[8] 帥春萍，徐保根，趙金鳳，等. 關(guān)于圖的符號(hào)圈點(diǎn)控制數(shù) [J].華東交通大學(xué)學(xué)報(bào)，2009,26(4):91-94.