潘晨佳, 曾慶厚

(福州大學(xué) 離散數(shù)學(xué)與理論計(jì)算機(jī)科學(xué)研究中心, 福建 福州 350003)

近幾年來,圖的控制理論研究的內(nèi)容越來越廣泛,各類圖的控制概念相繼產(chǎn)生且研究成果不斷豐富.關(guān)于圖的符號(hào)控制理論,其實(shí)早在1995年,Dunbar,Hedetniemi,Henning等人[1]就提出了圖的符號(hào)控制概念.近些年來,學(xué)者們對(duì)符號(hào)控制理論深入研究,得到了大量的研究成果.圖的符號(hào)控制理論,有著廣泛的應(yīng)用背景,例如在計(jì)算機(jī)網(wǎng)絡(luò)、交通運(yùn)輸、電網(wǎng)檢測(cè)[2,3]等方面.然而幾乎所有的概念都是與圖的點(diǎn)控制相關(guān), 很少涉及圖的邊控制問題.因此,徐保根[4]提出了圖的邊控制概念,并且研究了幾種類型的圖邊控制問題,提出了相關(guān)問題[5,6].

圖G=(V,E)是一個(gè)簡(jiǎn)單的有限無向圖,其中V表示圖G的頂點(diǎn)集,E表示圖G的邊集.考慮圖G中的任意一個(gè)點(diǎn)v∈V,任意一條邊e=uw∈E,我們用N(v),N(e)分別表示點(diǎn)v的所有鄰點(diǎn)構(gòu)成的集合以及與邊e=uw有公共端點(diǎn)的所有鄰邊構(gòu)成的集合,用N[e]=N(e)∪{e}表示e邊的閉鄰域.考慮子集S?V,G[S]表示子集S在圖G中的導(dǎo)出子圖.

E+={e∈E|f(e)=+1},E-={e∈E|f(e)=-1}.

定義頂點(diǎn)數(shù)為n的圖的符號(hào)邊控制數(shù)

問題1[4]: 對(duì)于任意頂點(diǎn)數(shù)為n的圖,其符號(hào)邊控制數(shù)g(n)是多少?

目前對(duì)于這個(gè)問題的研究,學(xué)者們得到了符號(hào)邊控制數(shù)的下界并且不斷進(jìn)行優(yōu)化:2009年,Akbari,Bolouki,Hatami等人[7]提出:對(duì)于任意正整數(shù)n,有g(shù)(n)≥-n2/16;2022年,Cherkashin,Prozorov[8]對(duì)這一下界進(jìn)行改進(jìn),證明了對(duì)于任意頂點(diǎn)數(shù)為n的圖,都有g(shù)(n)≥-n2/25.在文獻(xiàn)[9-11]中,研究了更多關(guān)于邊控制的問題.

在本文中,我們將討論無三角形圖的符號(hào)邊控制數(shù)g(n)的下界,并得到了以下的結(jié)果:

g(n)≥-0.02961n2.

1 前期準(zhǔn)備

本章節(jié)將給出本文定理1的證明中會(huì)用到的定理、引理及其證明.

引理3對(duì)于自變量為實(shí)數(shù)k,b的優(yōu)化問題

(*)

不妨假設(shè)k1∈[0,1],b1∈[0,1],滿足當(dāng)k=k1,b=b1時(shí),上述式子(*)達(dá)到最小值.

max(f(k1,b1),h(k1,b1))≥h(k1,b1)

max(f(k1,b1),h(k1,b1))≥f(k1,b1)

根據(jù)以上兩種情況,我們?nèi)菀椎玫?/p>

對(duì)T(b)進(jìn)行求導(dǎo),得到

當(dāng)T′(b)時(shí),則有18b3+18b2+3b-1=0.我們可以得到, 當(dāng)

有T′(b0)=0.并且當(dāng)b>b0,有T′(b)>0;當(dāng)b

2 定理1的證明

證明 設(shè)G=(V,E)是一個(gè)無三角形的圖,頂點(diǎn)數(shù)為n,f是圖G的一個(gè)符號(hào)邊控制函數(shù).根據(jù)符號(hào)邊控制函數(shù)f的定義,對(duì)于圖G中的任意一條e=uv∈E(G)邊都滿足su+sv-f(e)≥0,所以我們可以得到sv+su≥0.顯然我們可以將頂點(diǎn)集分為兩部分V=V+∪V-.

如果V-是個(gè)空集,那么顯然有

則定理1定成立.所以我們考慮V-非空的情況.

sy=|N+(y)|-|N-(y)|=-x,

即|N-(y)|≥-x.又因?yàn)閒是圖G的一個(gè)符號(hào)邊控制函數(shù),滿足任意一個(gè)頂點(diǎn)v∈N-(y),都有sy+sv≥0,所以有sv≥x>0.再根據(jù)V+的定義以及N-(y)?V+,有

(1)

容易得到,V-是個(gè)獨(dú)立集.反證,若存在G上的一條邊e=uv,且u,v∈V-,則su+sv<0,與f是圖G的一個(gè)符號(hào)邊控制函數(shù)矛盾.所以對(duì)于圖G上的任意一條邊e=ab∈E(G),至少存在一個(gè)端點(diǎn)滿足a∈V+或者b∈V+.因?yàn)閳DG是一個(gè)無三角形圖,所以顯然導(dǎo)出子圖G[V+]中也不存在三角形.由定理2,我們可以得到

從而有

即

(2)

由式子(1)和式子(2)可以得到以下式子,

(3)

故

(4)

所以結(jié)合式子(3)和式子(4)可得,

(5)

(6)

因?yàn)閳DG的頂點(diǎn)數(shù)為n,又由符號(hào)邊控制數(shù)g(n)的定義,結(jié)合式子(6)可得