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

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

本文中所指的圖均為無向簡單圖,文中未說明的符號和術(shù)語同于文獻[1]。

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

1 若干定義

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

文獻[8]中首先提出并研究了圖的圈符號控制。

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

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

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

證明由于δ≥2，圖G至少有一個圈，從而對圖G的每一個圈符號控制函數(shù)f，G中至少有兩個點v∈V(G)滿足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至少有兩個分支，由于δ≥2，G的每個分支中至少有一個導(dǎo)出圈，從而至少有一個導(dǎo)出圈C，使C上至多有A中一個點，故f(V(C))≤-1，矛盾。

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

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

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

給出圖的圈符號控制數(shù)的一個下界。

定理2 對于任意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

下面說明此下界是最好可能的。

對于一個無圈圖G，我們知道γsc(G)=-V(G)，這使得對于無圈圖來說，圖的圈符號控制數(shù)是已知的，無需研究。下面針對有圈圖給出圈符號控制數(shù)的一個下界。

定理3 對于任意n階圖G，E(G)=m，若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])≤

參考文獻：

[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)于圖的團符號控制數(shù)[J].系統(tǒng)科學(xué)與數(shù)學(xué), 2008, 3: 282-287.

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

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