圖的符號邊控制與減邊控制

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

（華東交通大學基礎科學學院，江西南昌330013）

1 引言及定義

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

設G=(V，E)為一個圖，e∈E，則NG(e)表示G中與e相鄰的邊集，稱為e的邊鄰域，NG[e]=NG(e)∪{e}為e的閉邊鄰域。(e)=|NG(e)|表示e在G中的邊度。NG(e)和NG[e]可分別簡記為N(e)和N[e]。若e=uv∈E(G)，則有d(e)=d(u)+d(v)-2。

近幾年來，圖的控制理論研究的內容越來越廣泛，各類控制概念相繼產生且研究成果不斷豐富，T.W.Haynes等人的專著［2］綜述了近幾些年來圖的控制理論研究方面的主要研究成果。然而，它們絕大多數均屬于圖的點控制，很少涉及到關于圖的邊控制問題和結果。2001年徐保根［3］首先提出了圖的符號邊控制概念，獲得了符號邊控制數的許多界限，并將這一概念推廣到邊上的多種符號控制，如符號星控制、符號圈控制、符號團控制、符號路控制等等。同樣地，這也產生了對應的減邊控制概念，從而使得控制理論研究內容和研究成果越來越豐富，徐保根專著［4］綜述了這些研究成果。

定義1.1［3］設G=(V，E)是一個非空圖，一個函數f:E→{- 1，+1} ：如果滿足f()≥1 對每一條邊e∈E(G)均成立，則稱f為圖G的一個符號邊控制函數。圖G的符號邊控制數記為(G)，定義(G)=min｛f(e)|f為G的一個符號邊控制函數｝。并且對于空圖G=，則定義(G)=0。

定義1.2［5］設G=(V，E)為一個非空圖，一個函數f:E→{-1，0，+1}被稱為圖G的一個減邊控制函數，如果對于G中每一條邊e均有f()≥1成立。圖G的減邊控制數定義為(G)=min｛f(e)|f為圖G的減邊控制函數｝，對于空圖G=，則同樣定義(G)=0。

比較上述兩個定義不難看出，圖G每一個符號邊控制函數均為G的一個減邊控制函數，從而有下面的引理1.1。

引理1.1對任意圖G，均有m(G)≤s(G)成立。

對于圖的符號邊控制數，目前人們已獲得了許多界限，文獻［3］中我們確定了一個具有m條邊的簡單圖的最小符號邊控制數，即下面的引理1.2。

引理1.2［3］設m≥1，ψ(m)表示m條邊圖的最小符號邊控制數，則有

由此引理，直接可得下面的引理1.3。

引理1.3對任意圖G，若|E(G) |=m≥1，則有

引理1.4［5］對任意圖G，若δ(G)≥1，則s(G)≥|V(G)| -|E(G) |，且此下界是最好可能的。

雖然人們已獲得了符號邊控制數的眾多下界，由引理1.1知，這些下界均不能作為減邊控制數的下界，可見本文探討減邊控制數的下界是非常有意義的。此外，在現有的關于(G)的界限中，幾乎都是依賴于圖的階數、邊數、最大度和最小度，本文給出其依賴于邊度序列的界限，并利用導出子圖，通過(G)的下界來確定m(G)的下界。

2 主要結果及其證明

前面介紹了圖的邊度概念，一條邊e∈E(G)的邊度是指在圖G中與e相鄰的邊數。對于一個非空圖G，若|E(G) |=m≥1，自然有邊度度序列()存在。同圖的（點）度序列一樣，圖的邊度序列常記為，即按邊度的大小進行排列。

設G=(V，E)為一個非空圖，S?E，f為圖G的一個符號邊控制函數或減邊控制函數，為了方便，在本文中我們記f(S)=f(e)。

定理2.1對任意圖G，若|E(G) |=m≥1且為其邊度序列。

令k0=min，則有(G)≥2k0-m。

證明設f為圖G的一個符號邊控制函數，且使得(G)=f(E)。由定義1.1知，對于每一條邊e∈E，均有f(N[e])≥1，故f(N[e])≥m，從而有

令：P={e∈E|f(e)=+1} ，M={e∈E|f(e)=-1} ，|P|=t，故有 |M|=m-t。

將k0的定義與（2）式比較得t≥k0，因此，(G)=2t-m≥2k0-m，定理證畢。

推論2.1對任意n階r-正則圖G，均有(G)≥。

證明由于G為一個n階r-正則圖，易見=2r-2(1 ≤i≤m)，由k0的定義中得到(2r-2)k-(2r-2)(m-k)≥2(m-k)，故k≥m=，因此，k0≥。

下面考慮圖的減邊控制數。與定理類似地可得到下面的結論。

定理2.2對任意圖G，若|E(G) |=m≥1且d′1 ≥d′2 ≥…≥d′m為其邊度序列。

則γ′m(G)≥min。

證明設f為圖G的一個減邊控制函數，且使得(G)=f(E)。由定義1.2 知，對于每一條邊e∈E，均有f(N[e])≥1，故f(N[e])≥m，從而有

令：P={e∈E|f(e)=+1} ，M={e∈E|f(e)=-1} ，Q={e∈E|f(e)=0} ，|P|=s，|M|=t，|Q|=m-s-t。由（3）式得

推論2.2對任意n階r-正則圖G，均有(G)≥。

證明由于G為n階r-正則圖，故=2r-2(1 ≤i≤m)，代入定理2.2中得出(2r-2)(s-t)≥m-(s-t)，故s-t≥，由定理2.2，推論2.2成立。

下面用一個圖G的所有子圖的最小符號邊控制數來表達G的減邊控制數的下界。若H為圖G的一個子圖，則用H?G來表示。

定理2.3對任意圖G，令π(G)=min{(H)|H?G} ，則(G)≥π(G)。

證明設f為圖G=(V，E)的減邊控制函數且使得(G)=f(E)，令X0={e∈E|f(e)=0} ，G0=G-X0

可見f0=為圖G0的一個符號控制函數，由于G0為G的子圖，從而有(G)=f(E)=f0(E(G0))≥γs(G0)≥π(G)，定理證畢。

由上述定理2.3可見，一個圖G的減控制數不小于其所有子圖的最小符號控制數，因此有下面的結論。

定理2.4如果存在一個遞減函數φ(t) ，使得對任意正整數t和任意具有t條邊的圖H，均有(H)≥φ(t)成立，則對任意具有m條邊的圖G，均有(G)≥φ(m)。

證明根據定理2.3，存在H?G，使得(H)=π(G)。令|E(H)| =r，故r≤m。

上述定理2.4告訴我們，如果找到了一個對任意m條邊的圖G都成立的的下界φ(m)，且φ(m)為m的遞減函數，則φ(m)也可作為的下界。

根據引理1.3，且注意到φ(m)=為一個關于m的遞減函數（m為非負整數），故由定理2.4可直接得到下面的定理。

定理2.5對任意一個具有m(m≥1)條邊的圖G，均有(G)≥φ(m)=。

3 若干注記

定義3.1設φ=φ(G)是一個包含圖G的若干參數的解析式，如果對任意圖G的任意子圖H?G，均有φ(H)≥φ(G)成立，則稱φ為圖的減性表達式，反之為增性表達式。

根據定理2.3，可將定理2.4推廣為如下的結論。

定理3.1如果存在一個關于圖的減性表達式φ，使得對任意圖H，均有(H)≥φ(H)成立，則對任意圖G，均有m(G)≥φ(G)。

猜想對任意圖G，若δ(G)≥1，則有m(G)≥|V(G) |-|E(G) |。

值得注意的是，類似的方法也可用在點控制中，參見文獻［7］，或許還可用在符號全控制中［8］及反符號邊控制［9］，這有待于進一步的研究。

［1］幫迪J A，默迪V S R.圖論及其應用［M］.上海：科學技術出版社，1984：5-35.

［2］HAYNES T W，HEDETNIEMI S T，SLATER P J.Domination in Graphs［M］.New York：Marcel Dekker，Inc.，1998：32-41.

［3］BAOGEN XU.On signed edge domination numbers of graphs［J］.Discrete Math，2001，239：179-189.

［4］徐保根.圖的控制理論［M］.北京：科學出版社，2008：130-153.

［5］BAOGEN XU.Two classes of edge domination in graphs［J］.Discrete Appl Math，2006，154：1541-1546.

［6］BAOGEN XU.On edge domination numbers of graphs［J］.Discrete Math，2005，294：311-316.

［7］BAOGEN XU.On minus domination and signed domination number in graphs［J］.J of Math Res and Exposition，2003（4）：586-590.

［8］趙金鳳，徐保根. On signed edge total domination numbers of graphs［J］. J of Math Res and Exposition，2011，32（2）：209-214.

［9］徐保根.關于圖的反符號邊控制［J］.華東交通大學學報，2007，24（5）：144-147.