偶圖符號控制數的下界

徐保根

（華東交通大學理學院，江西 南昌330013）

1 引言及定義

本文所指的圖均為無向簡單圖，文中未說明的符號和術語同于文獻［1-2］。

設G為一個圖，用V(G)和E(G)分別表示G的頂點集和邊集。對于任意頂點v∈V(G)，定義v的鄰域N(v)=｛u|uv∈E(G)｝，閉鄰域N[v]=N(v)?{v}。dG(v)= ||N(v) 為v點在G中的度，并且Δ=Δ(G)和δ=δ(G)分別表示圖G的最大度和最小度。若A和B為V(G)的兩個不交子集，則

圖的控制理論是圖論中的重要課題，近些年來，圖的控制概念有了許多新的變化，Cockayne E J等人［3］在符號控制的基礎上，引入了多種控制概念和控制參數，這在一定程度上改變了人們對控制理論的認識。自從文獻［4］中引入了圖的符號邊控制以來，各式各樣的邊控制概念和控制參數相繼產生，使得控制理論在內容上不斷豐富和完善，文獻［5］中綜述了近年來的主要研究成果。在文獻［6-8］中，我們探討了符號邊控制的一些下界，并研究了偶圖的符號邊控制數。在本文中，將探討偶圖的符號控制數的下界。

為了方便，若S?V(G)，f：V→R為一個實值函數，則記

下面給出關于圖的符號控制的定義。

定義1[3]設G=(V,E)是一個圖，一個實值函數f：V→{- 1, +1} 滿足f(N[u])≥1 對一切u∈V(G)都成立，則稱f為圖G的一個符號控制函數。圖G的符號控制數定義為

且稱滿足γs(G)=f(V)的符號控制函數為G的一個最小符號控制函數。

2 主要結果及證明

本文主要給出偶圖的符號控制數的兩個下界，它們分別依賴于圖的最大度和最小度。

定理1對于任意n階偶圖G，若Δ=Δ(G)表示圖G的最大度，則有

證明記G=(V,E)，并且V=V1?V2為偶圖G的2-部頂點劃分，其中 ||Vi=ni(1 ≤i≤2)，n1+n2=n。

設f為圖G的一個最小符號控制函數，即有

令A={v∈V|f(v)=+1} ，B={v∈V|f(v)=-1} ，|A|=s，|B|=n-s，顯然有γs(G)=f(V)= |A|- |B|=2s-n。

記A1=A?V1，A2=A?V2，B1=B?V1，B2=B?V2。可見，V1=A1?B1，V2=A2?B2，并且A=A1?A2，B=B1?B2。

對于每個v∈B1，由定義知f(N[v])≥1，故v點至少與A中的兩個點相鄰，又因為G為偶圖，即v點與A1中的點均不相鄰，從而知v點至少與A2中的兩個點相鄰，故B1與A2之間的邊數 |E(B1,A2) |≥2 |B1|。同理，B2與A1之間的邊數 |E(B2,A1) |≥2 |B2|。

故A2中至少有一個點u，使得u點鄰接B1中的點數不少于。由于f(N[u])≥1，且A2?V2為點獨立集，故u點鄰接A1中的點數也不少于

定理2對于任意n階偶圖G，若δ=δ(G)表示圖G的最小度，則有

證明記偶圖G=(V1?V2,E)，其中V=V1?V2為偶圖的二部點集劃分。設f為圖G的一個最小符號控制函數，即有γs(G)=f(V) 。與定理1 證明同樣地，令A={v∈V|f(v)=+1} ，B={v∈V|f(v)=-1} ，|A|=s，|B|=n-s，顯然有γs(G)=f(V)= |A|- |B|=2s-n。記A1=A?V1，A2=A?V2，B1=B?V1，B2=B?V2?？梢?，V1=A1?B1，V2=A2?B2，并且A=A1?A2，B=B1?B2。

對于對于每個v∈B1，由定義知f(N[v])≥1，注意到G為偶圖，故v點至少與A2中個點相鄰，即有。從而A2中存在一點u∈A2，使得u點與B1中至少個點相鄰。又由定義知f(N[u])≥1，故u點與A1中至少個點相鄰，即有，從而2 ||A1· ||A2≥ ||B2(δ+2)，完全類似地也可得到2 ||A1· ||A2≥ ||B1(δ+2)。將兩式相加得

注意到

導出

至此，定理2證畢。

[1] BONDYJ A,MURTY V S R.Graph Theory with Applications[M].Amsterdam:Elsevier,1976.

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

[3] COCKAYNE E J, MYNHARDT C M.On a generalization of signed dominating function of graphs[J].Ars Combin,1996,46:235-245.

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

[5] 徐保根.圖的控制與染色理論[M].武漢:華中科技大學出版社,2013:11.

[6] 徐保根.關于圖的符號邊控制數的下界[J].華東交通大學學報,2004,21(1):110-113

[7] 徐保根.一類偶圖的符號邊控制數[J].華東交通大學學報,2004,21(2):124-126

[8] 趙金鳳,徐保根.關于圖的符號邊控制數的下界[J].江西師大學報:自然科學版,2010,43(1):27-29.