無三角形圖的符號邊控制數下界

潘晨佳, 曾慶厚

(福州大學 離散數學與理論計算機科學研究中心, 福建 福州 350003)

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

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

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

定義頂點數為n的圖的符號邊控制數

問題1[4]: 對于任意頂點數為n的圖,其符號邊控制數g(n)是多少?

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

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

g(n)≥-0.02961n2.

1 前期準備

本章節將給出本文定理1的證明中會用到的定理、引理及其證明.

引理3對于自變量為實數k,b的優化問題

(*)

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

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

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

根據以上兩種情況,我們容易得到

對T(b)進行求導,得到

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

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

2 定理1的證明

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

如果V-是個空集,那么顯然有

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

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

即|N-(y)|≥-x.又因為f是圖G的一個符號邊控制函數,滿足任意一個頂點v∈N-(y),都有sy+sv≥0,所以有sv≥x>0.再根據V+的定義以及N-(y)?V+,有

(1)

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

從而有

即

(2)

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

(3)

故

(4)

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

(5)

(6)

因為圖G的頂點數為n,又由符號邊控制數g(n)的定義,結合式子(6)可得