尚華輝， 苗連英

(1.永城職業(yè)學(xué)院 基礎(chǔ)部， 河南 永城 476600；2.中國(guó)礦業(yè)大學(xué) 數(shù)學(xué)學(xué)院， 江蘇 徐州 221116)

0 引言

圖的控制函數(shù)是圖的控制理論中的一個(gè)重要組成部分.圖的符號(hào)控制函數(shù)有著重要的應(yīng)用背景，因而確定其下界有重要的意義.

為了方便,對(duì)于?v∈V(G),將dG(v)簡(jiǎn)記為d(v).凡文中未提到的術(shù)語見文獻(xiàn)[1-4].

在下述定義1的符號(hào)控制函數(shù)中，f(x)表示頂點(diǎn)x在雙值函數(shù)f映射下的函數(shù)值，記A={v∈V|f(v)=1},B={v∈V|f(v)=-1},f(N[x])表示N[x]中的頂點(diǎn)所對(duì)應(yīng)的函數(shù)值的和，f(V)表示頂點(diǎn)集V中的頂點(diǎn)所對(duì)應(yīng)的函數(shù)值的和.

定義1[2]設(shè)G=(V,E)為一個(gè)圖，對(duì)點(diǎn)集V(G)定義雙值函數(shù)f：V→{-1,+1},若對(duì)于任意的v∈V,均有f(N[v])≥1成立,則稱f為圖G的一個(gè)符號(hào)控制函數(shù)，并稱γs(G)=min{f(V)|f為G的符號(hào)控制函數(shù)}為圖G的符號(hào)控制數(shù).

下面給出本文要用到的結(jié)論.

1 主要結(jié)果

證明設(shè)f為圖G的符號(hào)控制函數(shù)且使得γs(G)=f(V).令A(yù)={v∈V|f(v)=1},B={v∈V|f(v)=-1},|A|=t,則|B|=n-t,且γs=|A|-|B|=2t-n.

?x∈B,且d(x)=3時(shí)，由符號(hào)控制函數(shù)的定義知f(N[x])≥1,則有{y|x的鄰點(diǎn)}?A,即dG[{x}∪A](x)=3.

解之得

故有

易驗(yàn)證δ≥3時(shí)，此下界改進(jìn)了結(jié)論1中的下界.

下面驗(yàn)證定理1中的下界是最好可能的.

證明設(shè)f為圖G的符號(hào)控制函數(shù)且滿足γs(G)=f(V).

記|A|=t,則|B|=n-t,γs=|A|-|B|=2t-n.

記m1=|E(G[A])|,則|E(G[B])|=m-m1-|E(A,B)|.

記Ao={x|d(x)=1(mod 2),x∈A},Bo={x|d(x)=1(mod 2),x∈B}.

對(duì)于?x∈A-Ao,有|N(x)∩A|≥|N(x)∩B|,對(duì)于?x∈Ao,有|N(x)∩A|≥|N(x)∩B|+1.

對(duì)于?x∈B-Bo,有|N(x)∩A|≥|N(x)∩B|+2,對(duì)于?x∈Bo,有|N(x)∩A|≥|N(x)∩B|+3.

從而有

(1)

由式(1)中的不等式2m1≥2{m-m1-|E(A,B)|}+2|B|+|O(G)|得

(2)

由式(1)和式(2)得不等式

(3)

由不等式(3)得

(4)

由式(1)中的t(t-1)≥2m1得

(5)

由式(4)和式(5)得

易驗(yàn)證m≥3n時(shí)，此下界改進(jìn)了結(jié)論2中的下界.

證明設(shè)f為圖G的符號(hào)控制函數(shù)且使得γs(G)=f(V).與定理1中的證明類似，得到

|E(A,B)|≥3(n-t).

(6)

由符號(hào)控制函數(shù)的定義知頂點(diǎn)x與點(diǎn)集A的鄰點(diǎn)數(shù)不少于與點(diǎn)集B的鄰點(diǎn)數(shù)，即?x∈A,dG[{x}∪A](x)≥dG[{x}∪B](x),故有

(7)

由式(6)和式(7)得

2|E(G[A])|≥|E(A,B)|≥3(n-t),

(8)

即有

(9)

結(jié)合式(8)、式(9)及圖的結(jié)構(gòu)知

m≥|E(G[A])|+|E(A,B)|≥

從而有

易驗(yàn)證δ≥3時(shí)，此下界改進(jìn)了結(jié)論3中的下界.

下面驗(yàn)證定理3中的下界是最好可能的.

2 結(jié)論

得到了符號(hào)控制數(shù)的3個(gè)下界，這3個(gè)下界分別改進(jìn)了引言中結(jié)論1、結(jié)論2、結(jié)論3中的結(jié)果.此外，還給出了滿足上述2個(gè)下界的圖.