圖的符號(hào)邊控制與減邊控制

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

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

1 引言及定義

本文中所指的圖均為無(wú)向簡(jiǎn)單圖，文中未說(shuō)明的符號(hào)和術(shù)語(yǔ)同于文獻(xiàn)［1］。

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

近幾年來(lái)，圖的控制理論研究的內(nèi)容越來(lái)越廣泛，各類(lèi)控制概念相繼產(chǎn)生且研究成果不斷豐富，T.W.Haynes等人的專(zhuān)著［2］綜述了近幾些年來(lái)圖的控制理論研究方面的主要研究成果。然而，它們絕大多數(shù)均屬于圖的點(diǎn)控制，很少涉及到關(guān)于圖的邊控制問(wèn)題和結(jié)果。2001年徐保根［3］首先提出了圖的符號(hào)邊控制概念，獲得了符號(hào)邊控制數(shù)的許多界限，并將這一概念推廣到邊上的多種符號(hào)控制，如符號(hào)星控制、符號(hào)圈控制、符號(hào)團(tuán)控制、符號(hào)路控制等等。同樣地，這也產(chǎn)生了對(duì)應(yīng)的減邊控制概念，從而使得控制理論研究?jī)?nèi)容和研究成果越來(lái)越豐富，徐保根專(zhuān)著［4］綜述了這些研究成果。

定義1.1［3］設(shè)G=(V，E)是一個(gè)非空?qǐng)D，一個(gè)函數(shù)f:E→{- 1，+1} ：如果滿(mǎn)足f()≥1 對(duì)每一條邊e∈E(G)均成立，則稱(chēng)f為圖G的一個(gè)符號(hào)邊控制函數(shù)。圖G的符號(hào)邊控制數(shù)記為(G)，定義(G)=min｛f(e)|f為G的一個(gè)符號(hào)邊控制函數(shù)｝。并且對(duì)于空?qǐng)DG=，則定義(G)=0。

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

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

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

對(duì)于圖的符號(hào)邊控制數(shù)，目前人們已獲得了許多界限，文獻(xiàn)［3］中我們確定了一個(gè)具有m條邊的簡(jiǎn)單圖的最小符號(hào)邊控制數(shù)，即下面的引理1.2。

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

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

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

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

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

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

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

設(shè)G=(V，E)為一個(gè)非空?qǐng)D，S?E，f為圖G的一個(gè)符號(hào)邊控制函數(shù)或減邊控制函數(shù)，為了方便，在本文中我們記f(S)=f(e)。

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

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

證明設(shè)f為圖G的一個(gè)符號(hào)邊控制函數(shù)，且使得(G)=f(E)。由定義1.1知，對(duì)于每一條邊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對(duì)任意n階r-正則圖G，均有(G)≥。

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

下面考慮圖的減邊控制數(shù)。與定理類(lèi)似地可得到下面的結(jié)論。

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

則γ′m(G)≥min。

證明設(shè)f為圖G的一個(gè)減邊控制函數(shù)，且使得(G)=f(E)。由定義1.2 知，對(duì)于每一條邊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對(duì)任意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ào)邊控制數(shù)來(lái)表達(dá)G的減邊控制數(shù)的下界。若H為圖G的一個(gè)子圖，則用H?G來(lái)表示。

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

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

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

由上述定理2.3可見(jiàn)，一個(gè)圖G的減控制數(shù)不小于其所有子圖的最小符號(hào)控制數(shù)，因此有下面的結(jié)論。

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

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

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

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

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

3 若干注記

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

根據(jù)定理2.3，可將定理2.4推廣為如下的結(jié)論。

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

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

值得注意的是，類(lèi)似的方法也可用在點(diǎn)控制中，參見(jiàn)文獻(xiàn)［7］，或許還可用在符號(hào)全控制中［8］及反符號(hào)邊控制［9］，這有待于進(jìn)一步的研究。

［1］幫迪J A，默迪V S R.圖論及其應(yīng)用［M］.上海：科學(xué)技術(shù)出版社，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］.北京：科學(xué)出版社，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］徐保根.關(guān)于圖的反符號(hào)邊控制［J］.華東交通大學(xué)學(xué)報(bào)，2007，24（5）：144-147.