圖的反符號邊控制數的新上界*

丁宗鵬

湖南第一師范學院數學與計算科學學院，湖南 長沙 410205

本文中所指的圖均為無向簡單圖，頂點集為V，邊集為E。沒有說明的術語和符號參照文獻［1］。設G=(V，E)為一個圖，對于任意頂點v∈V，則NG(v)表示G中與v相鄰的點集，稱為v的鄰域，NG[v]=NG(v) ∪{v}為v點在G中的閉鄰域。dG(v) =| |NG(v) 表示v在G中的度。若一個圖中每個頂點的度都為r，則稱這個圖為r正則圖。NG(v)，NG[v]，dG(v)可分別簡記為N(v)，N[v]，d(v). 記Δ 和δ分別為圖G的最大度和最小度。

類似地，對任意邊e∈E(G)，則NG(e) 表示G中與e相鄰的邊集，稱為e的邊鄰域，NG[e]=NG(e) ∪{e}為e點在G中的閉邊鄰域。dG(e) =| |NG(e) 表示e在G中的邊度，NG(e)，NG[e]，dG(e)可分別簡記為N(e)，N[e]，d(e). 記Δ′和δ′分別為圖G的最大度和最小度。

記圖G=(V，E)的頂點數為n，邊數為m. 若e=uv∈E，我們不難得到d(e)=d(u) +d(v) - 2，于是2δ- 2 ≤d(e)≤2Δ - 2，且有

近年來，圖的控制理論的研究日趨活躍，相繼產生了各種控制概念。圖的很多不同類型的控制概念及其變化形式被Cockayne 等［2］先后引入。Haynes 等［3-4］中闡述了目前所取得的主要研究成果。但是大多概念和結論都是圍繞圖的點控制展開，而圖的邊控制涉及不多。Xu在文獻［5］中率先引入圖的符號邊控制概念，并在此基礎上展開相關研究［6-7］。文獻［8］定義了圖的逆符號邊控制，并研究了逆符號邊控制數的上界。其他關于圖控制數的相關結果可參考文獻［9-13］。本文我們首先引入圖的反符號邊控制的定義，給出一般圖的反符號邊控制數的若干新上界，并且證明這些上界都是可達的。

1 反符號邊控制數的概念及性質

問題的提出：將一個圖的邊集E劃分為E1和E2，使得G中每條邊的閉鄰域中第一類邊不多于第二類邊，問這兩類邊的數目之差 |E1|-|E2|最多是多少？

2 反符號邊控制數的新上界

為了方便，設R是一個實數集，且f：E→R是一個函數，S?E(G)，則記f(S) =. 并且，將f(N[e])記為f[e]. 用Pn表示具有n個頂點的一條路，用Kn表示具有n個頂點的完全圖。

定理1 對于任意n階連通圖G，其邊數為m，邊度為奇數的邊共n0條，則有

且此上界是可達的。

證明 設f為圖G的一個最大的反符號邊控制函數，且(G) =f(E).

令

P={e∈E|f(e) = 1} ,P0={e∈P|d(e)為奇數} ,Pe=P-P0;Q={e∈E|f(e) =-1},Q0={e∈Q|d(e)為奇數}，Qe=Q-Q0. |P|=p，|Q|=q，|P0|=p0，|Pe|=pe，|Q0|=q0，|Qe|=qe.依照圖的反符號邊控制的定義，對任意e∈E(G)，f[e]≤0. 于是有

因此

即

綜合式（1）和式（2）得

注意到p=m-q，由式（3）得

綜上所述得

定理2 對于任意n階連通圖G，其邊數為m，Δ′，δ′分別是其最大邊度與最小邊度，邊度為奇數的邊共n0條，則有

且此上界是可達的。

證明 設f為圖G的一個最大的反符號邊控制函數，且(G) =f(E).

令

依定義知，對任意e∈E0，f[e]≤0；對任意e∈Ee，f[e]≤-1.于是有

另外，

所以

至此式（5）得證。

于是

從而

由式（4）和式（8）得

又由式（4）和式（9）得

綜上可得

證明 由定理2的證明

可得

即

于是