圖的全局2-彩虹控制數的上界

曾淑婷，郝國亮

(東華理工大學理學院，330013，南昌)

1 預備知識

隨著科學技術和實際問題的發展，圖的控制理論的內容越來越豐富，具有越來越廣泛的應用[1-2]。基于不同的實際背景和歷史背景，圖的控制數衍生出許多新的控制參數[3-7]。圖的彩虹控制問題最早是在2005年被提出的[8]，由于確定一般圖的彩虹控制數是NP完全的[9]，為此，許多學者著重研究圖的彩虹控制數的界或特殊圖的彩虹控制數的精確值[10-11]。Alqesmah等給出了完全圖、完全二部圖和輪圖的全局彩虹控制數的精確值，并刻畫了全局彩虹控制數等于頂點數的連通圖[12]。Amjadi等探究了圖的全局彩虹控制數的上下界[13]。本文將根據圖的直徑、最小度和圍長等研究圖的全局2-彩虹控制數的上界。

2 主要結果

首先給出Alqesmah等[12]得到的關于路的全局2-彩虹控制數的如下結果，這將在后續證明中多次使用。

引理1[12]： 設P=v1v2…vd+1是含有d+1個頂點的路(d≥5)，則γgr2(P)=?(d+1)/2」+1且存在一個γgr2(P)-函數g:V(P)→2{1,2}，使得

其中：當d+1≡1,3(mod4)時，X={i|i≡3(mod4)且i≤d+1};當d+1≡0,2(mod4)時，X={i|i≡3(mod4)且i

下面給出直徑至少為5的圖的全局2-彩虹控制數的上界。

定理1：設G是階為n的連通圖且d=d(G)≥5，則

γgr2(G)≤n-「(d+1)/2?+1。

證明：設P=v1v2…vd+1是圖G的一條直徑路且設g:V(P)→2{1,2}是如引理1所示的γgr2(P)-函數，則由引理1知，ω(g)=γgr2(P)=?(d+1)/2」+1。定義圖G的一個全局2-彩虹控制函數f:V(G)→2{1,2}使得當v∈V(P)時，f(v)=g(v)且當v∈V(G)V(P)時，f(v)={1}。因此

γgr2(G)≤ω(f)=ω(g)+|V(G)V(P)|=?(d+1)/2」+1+(n-(d+1))=n-「(d+1)/2?+1。

為改進定理1的上界，下面考慮最小度至少為2和圍長至少為4的圖。

定理2：設G是階為n的連通圖且d=d(G)≥5,δ=δ(G)≥2,g(G)≥4，則

證明：設P=v1v2…vd+1是圖G的一條直徑路且設g:V(P)→2{1,2}是如引理1所示的γgr2(P)-函數，則ω(g)=γgr2(P)=?(d+1)/2」+1。令X=N(v1)V(P)且Y=N(vd+1)V(P)。

斷言1：|X|≥δ-1且|Y|≥δ-1。

斷言1的證明：由于P是圖G的一條直徑路，則N(v1)∩V(P)={v2},又因為δ(G)≥2,所以|X|=|N(v1)V(P)|≥δ-1。同理可得|Y|=|N(vd+1)V(P)|≥δ-1。斷言1得證。

斷言2：對任意u∈X,u在(V(G)(V(P)∪{u}))∪{v3}中至少有一個鄰點。

斷言2的證明：因為g(G)≥4,所以對任意u∈X,均有v2?N(u);又因為P是圖G的一條直徑路，所以對任意u∈X,v4,v5,…,vd+1?N(u)。此外，由于δ(G)≥2,則對任意u∈X,u在∪{v3}中至少有一個鄰點。斷言2得證。

斷言3：對任意u∈Y,u在(V(G)(V(P)∪{u}))∪{vd-1}中至少有一個鄰點。

斷言3的證明：類似于斷言2的證明可得，斷言3成立。

下面分以下2種情形討論。

情形1：d+1≡0,2(mod4)。

由斷言2，不難看出函數f:V(G)→2{1,2}使得

是圖G的全局2-彩虹控制函數。因此由斷言1知，

γgr2(G)≤ω(f)=ω(g)+n-(|V(P)|+|X|)≤?(d+1)/2」+1+n-(d+1+δ-1)=(d+1)/2+1+n-d-δ=n-(d-3)/2-δ。

情形2：d+1≡1,3(mod4)。

由于P是圖G的一條直徑路，則對任意u∈X且v∈Y,有uv?E(G)且N(u)∩N(v)=?成立。注意到當d+1≡1(mod4)時，g(vd+1)={1};當d+1≡3(mod4)時，g(vd+1)={2}。故由斷言2和斷言3知，函數f:V(G)→2{1,2}使得

是圖G的全局2-彩虹控制函數。因此由斷言1知，

γgr2(G)≤ω(f)=ω(g)+n-(|V(P)|+|X|+ |Y|)≤?(d+1)/2」+1+n-(d+1+2(δ-1))=d/2+1+n-d+1-2δ=n-d/2-2δ+2。

對于圍長至少為5的圖，進一步改進定理2的上界。

定理3：設G是階為n的連通圖且d=d(G)≥5,δ=δ(G)≥2,g(G)≥5，則

γgr2(G)≤n-2δ-「(d+1)/2?+3。

證明：設P=v1v2…vd+1是圖G的一條直徑路且設g:V(P)→2{1,2}是如引理1所示的γgr2(P)-函數，則由引理1知，ω(g)=γgr2(P)=?(d+1)/2」+1。令X=N(v1)V(P)且Y=N(vd+1)V(P)。類似于定理2中斷言1的證明可得|X|≥δ-1且|Y|≥δ-1。類似于定理2中斷言2和斷言3的證明可得，對任意u∈X∪Y,u在V(G)(V(P)∪{u})中至少有一個鄰點。因為P是圖G的一條直徑路，所以對任意u∈X和v∈Y,均有uv?E(G)且N(u)∩N(v)=?成立。注意到當d+1≡1(mod4)時，g(vd+1)={1};當d+1≡0,2,3(mod4)時，g(vd+1)={2}，則不難看出函數f:V(G)→2{1,2}使得

是圖G的全局2-彩虹控制函數。因此

γgr2(G)≤ω(f)=ω(g)+n-(|V(P)|+|X|+ |Y|)≤?(d+1)/2」+1+n-(d+1+2(δ-1))=n-2δ-「(d+1)/2?+3。

對于最小度至少為3的圖，將部分改進定理3的上界。

定理4：設G是一個階為n的連通圖且d=d(G)≥5,δ=δ(G)≥3，則

γgr2(G)≤n-d+?d/3」-(δ-3)「d/3?。

證明：設P=v1v2…vd+1是圖G的一條直徑路。定義P的一個全局2-彩虹控制函數g:V(G)→2{1,2}使得

|N(X)V(P)|=∑u∈X|N(u)V(P)|≥|X|(δ-2)=「d/3?(δ-2)。

故不難看出函數f:V(G)→2{1,2}使得

是圖G的全局2-彩虹控制函數。因此

γgr2(G)≤ω(f)=ω(g)+n-(|V(P)|+|N(X)V(P)|)≤「d/3?+?d/3」+1+n-(d+1+「d/3?(δ-2))=n-d+?d/3」-(δ-3)「d/3?。

對于圍長至少為7的圖，將繼續改進定理4的上界。

定理5：設G是階為n的連通圖且d=d(G)≥5,δ=δ(G)≥3,g(G)≥7，則

γgr2(G)≤n-d-δ-(δ-3)?(d+1)/2」。

證明：設P=v1v2…vd+1是圖G的一條直徑路且設g:V(P)→2{1,2}是如引理1所示的γgr2(P)-函數，則由引理1知，ω(g)=γgr2(P)=?(d+1)/2」+1。令V1={vi∈V(P)|g(vi)={1}}且V2={vi∈V(P)|g(vi)={2}}，則|V1∪V2|=ω(g)=?(d+1)/2」+1。因為P是圖G的一條直徑路且g(G)≥7,所以對于任意u,v∈V1∪V2,N(u)∩N(v)=?。類似于定理2中斷言1的證明可得，|N(v1)V(P)|≥δ-1,|N(vd+1)V(P)|≥δ-1且對任意u∈(V1∪V2){v1,vd+1},|N(u)V(P)|≥δ-2。令X=N(V1)V(P)且Y=N(V2)V(P)，于是

|X|+|Y|=|N(v1)V(P)|+|N(vd+1)V(P)|+∑u∈(V1∪V2){v1,vd+1}|N(u)V(P)|≥2(δ-1)+(?(d+1)/2」-1)(δ-2)=δ+?(d+1)/2」(δ-2)。

由于P是圖G的一條直徑路且g(G)≥7,則對任意2個頂點u,v∈X∪Y,均有uv?E(G)且N(u)∩N(v)=?成立。于是不難看出函數f:V(G)→2{1,2}使得

是圖G的全局2-彩虹控制函數。因此

γgr2(G)≤ω(f)=ω(g)+n-(|V(P)|+|X|+ |Y|)≤?(d+1)/2」+1+n-(d+1+δ+(d+1)/2」(δ-2))=n-d-δ-(δ-3)?(d+1)/2」。

下面利用圍長給出圖的全局2-彩虹控制數的一個上界。

定理6：設G是階為n的連通圖且g(G)≥6，則

γgr2(G)≤n-「g(G)/2?+「g(G)/4?-?g(G)/4」。

證明：設V(G)={v1,v2,…,vn}且不妨設C=v1v2…vg(G)v1是圖G的一個長為g(G)的圈。當g(G)≡0,1,3(mod4)時，令X={i≤g(G)|i≡0,2(mod4)};當g(G)≡2(mod4)時，令X={i

是圖G的全局2-彩虹控制函數。因此

γgr2(G)≤ω(f)=n-|X|=n-「g(G)/2?+「g(G)/4?-?g(G)/4」。