圖的全局2-彩虹控制數(shù)的上界

曾淑婷，郝國(guó)亮

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

1 預(yù)備知識(shí)

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

2 主要結(jié)果

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

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

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

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

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

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

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

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

為改進(jìn)定理1的上界，下面考慮最小度至少為2和圍長(zhǎng)至少為4的圖。

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

證明：設(shè)P=v1v2…vd+1是圖G的一條直徑路且設(shè)g:V(P)→2{1,2}是如引理1所示的γgr2(P)-函數(shù)，則ω(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},又因?yàn)棣?G)≥2,所以|X|=|N(v1)V(P)|≥δ-1。同理可得|Y|=|N(vd+1)V(P)|≥δ-1。斷言1得證。

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

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

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

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

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

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

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

是圖G的全局2-彩虹控制函數(shù)。因此由斷言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的一條直徑路，則對(duì)任意u∈X且v∈Y,有uv?E(G)且N(u)∩N(v)=?成立。注意到當(dāng)d+1≡1(mod4)時(shí)，g(vd+1)={1};當(dāng)d+1≡3(mod4)時(shí)，g(vd+1)={2}。故由斷言2和斷言3知，函數(shù)f:V(G)→2{1,2}使得

是圖G的全局2-彩虹控制函數(shù)。因此由斷言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。

對(duì)于圍長(zhǎng)至少為5的圖，進(jìn)一步改進(jìn)定理2的上界。

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

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

證明：設(shè)P=v1v2…vd+1是圖G的一條直徑路且設(shè)g:V(P)→2{1,2}是如引理1所示的γgr2(P)-函數(shù)，則由引理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的證明可得，對(duì)任意u∈X∪Y,u在V(G)(V(P)∪{u})中至少有一個(gè)鄰點(diǎn)。因?yàn)镻是圖G的一條直徑路，所以對(duì)任意u∈X和v∈Y,均有uv?E(G)且N(u)∩N(v)=?成立。注意到當(dāng)d+1≡1(mod4)時(shí)，g(vd+1)={1};當(dāng)d+1≡0,2,3(mod4)時(shí)，g(vd+1)={2}，則不難看出函數(shù)f:V(G)→2{1,2}使得

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

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

對(duì)于最小度至少為3的圖，將部分改進(jìn)定理3的上界。

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

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

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

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

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

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

γ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?。

對(duì)于圍長(zhǎng)至少為7的圖，將繼續(xù)改進(jìn)定理4的上界。

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

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

證明：設(shè)P=v1v2…vd+1是圖G的一條直徑路且設(shè)g:V(P)→2{1,2}是如引理1所示的γgr2(P)-函數(shù)，則由引理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。因?yàn)镻是圖G的一條直徑路且g(G)≥7,所以對(duì)于任意u,v∈V1∪V2,N(u)∩N(v)=?。類似于定理2中斷言1的證明可得，|N(v1)V(P)|≥δ-1,|N(vd+1)V(P)|≥δ-1且對(duì)任意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,則對(duì)任意2個(gè)頂點(diǎn)u,v∈X∪Y,均有uv?E(G)且N(u)∩N(v)=?成立。于是不難看出函數(shù)f:V(G)→2{1,2}使得

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

γ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」。

下面利用圍長(zhǎng)給出圖的全局2-彩虹控制數(shù)的一個(gè)上界。

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

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

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

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

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