郝 國(guó) 亮, 曾 淑 婷, 莊 蔚, 謝 智 紅

(1.東華理工大學(xué) 理學(xué)院,江西 南昌 330013;2.菏澤學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,山東 菏澤 274015;3.廈門理工學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,福建 廈門 361024;4.菏澤學(xué)院 商學(xué)院,山東 菏澤 274015 )

0 引 言

圖的控制理論是圖論中一個(gè)重要的研究領(lǐng)域,基于不同的研究背景,圖的經(jīng)典控制數(shù)衍生出了許多不同類型的控制參數(shù)[1-3],其中圖的彩虹控制數(shù)的概念最早出現(xiàn)于2008年[4].隨后,研究者們陸續(xù)給出了彩虹控制數(shù)的許多研究成果[5-8].Alqesmah等[9]和Amjadi等[10]分別引入了彩虹控制數(shù)的一個(gè)衍生變量,即圖的全局彩虹控制數(shù).Amjadi等[10]刻畫了全局2-彩虹控制數(shù)與2-彩虹控制數(shù)之差為1和2的樹(shù).受此結(jié)果的啟發(fā),本文主要刻畫全局3-彩虹控制數(shù)與3-彩虹控制數(shù)之差為2和3的所有樹(shù).

1 基本概念

稱無(wú)圈的連通圖為樹(shù).在樹(shù)中,度為1的頂點(diǎn)稱為葉子點(diǎn),只與1個(gè)葉子點(diǎn)相鄰的頂點(diǎn)稱為弱支撐點(diǎn),至少與2個(gè)葉子點(diǎn)相鄰的頂點(diǎn)稱為強(qiáng)支撐點(diǎn),弱支撐點(diǎn)和強(qiáng)支撐點(diǎn)統(tǒng)稱為支撐點(diǎn).雙星圖Sp,q是指恰好有2個(gè)支撐點(diǎn)的樹(shù)且它們分別與p和q個(gè)葉子點(diǎn)相鄰.稱n≥3階完全二部圖K1,n-1為星形圖,且稱度為n-1的頂點(diǎn)為其中心.病態(tài)蜘蛛樹(shù)是指對(duì)星形圖K1,n-1(n≥3)至多剖分n-2條邊所得到的圖,稱星形圖的中心為病態(tài)蜘蛛樹(shù)的頭,稱與頭距離為1和2的葉子點(diǎn)分別為病態(tài)腳和健康腳.用Π表示有2個(gè)健康腳且至少有3個(gè)病態(tài)腳的病態(tài)蜘蛛樹(shù)構(gòu)成的集合.

2 主要結(jié)論

為得到本文的主要結(jié)果,首先給出下列引理.

引理1設(shè)u是樹(shù)T中至少與3個(gè)葉子點(diǎn)相鄰的強(qiáng)支撐點(diǎn),則一定存在一個(gè)γr3(T)-函數(shù)f使得f(u)={1,2,3}且對(duì)任意與u相鄰的葉子點(diǎn)x,f(x)=?.

γr3(T)≤ω(f)=

ω(h)+3-3=

ω(h)=

γr3(T)

因此ω(f)=γr3(T).意味著f也是一個(gè)γr3(T)-函數(shù).故f就是所求的γr3(T)-函數(shù).

引理2設(shè)P=u1u2u3u4u5是樹(shù)T中的一條路使得d(u1)=d(u5)=1且d(u2)=d(u4)=2,則一定存在一個(gè)γr3(T)-函數(shù)f使得f(u1)=f(u5)={1},f(u2)=f(u4)=?且{2,3}?f(u3).

證明設(shè)h是一個(gè)γr3(T)-函數(shù).因?yàn)閐(u1)=d(u5)=1,所以|h(u1)|+|h(u2)|≥1且|h(u4)|+|h(u5)|≥1.如果|h(u1)|+|h(u2)|=1或|h(u4)|+|h(u5)|=1,則不妨設(shè)|h(u1)|+|h(u2)|=1.于是由γr3(T)-函數(shù)的定義知,|h(u1)|=1且h(u2)=?.因此不妨設(shè)h(u1)={1}.又因?yàn)镹(u2)={u1,u3},所以h(u1)∪h(u3)={1,2,3},于是{2,3}?h(u3).注意到d(u4)=2且d(u5)=1,因此由γr3(T)-函數(shù)的定義知:如果h(u3)={2,3},則h(u4)=?且h(u5)={1};如果h(u3)={1,2,3},則h(u4)=?且|h(u5)|=1.于是不妨設(shè)h(u5)={1}.故在這種情況下,f=h就是所求的γr3(T)-函數(shù).

如果|h(u1)|+|h(u2)|≥2且|h(u4)|+|h(u5)|≥2,則定義樹(shù)T的一個(gè)3-彩虹控制函數(shù)f:V(T)→2{1,2,3}使得f(u1)=f(u5)={1},f(u2)=f(u4)=?,f(u3)=h(u3)∪{2,3}且當(dāng)x?{u1,u2,…,u5}時(shí),f(x)=h(x).于是

γr3(T)≤ω(f)=

ω(h)+(|f(u1)|+|f(u2)|+

|f(u4)|+|f(u5)|)-(|h(u1)|+

|h(u2)|+|h(u4)|+|h(u5)|)+

(|f(u3)|-|h(u3)|)≤

ω(h)+2-4+(|h(u3)∪{2,3}|-

|h(u3)|)≤

ω(h)=

γr3(T)

因此ω(f)=γr3(T).意味著f也是一個(gè)γr3(T)-函數(shù).故f就是所求的γr3(T)-函數(shù).

引理3設(shè)u1是樹(shù)T中與葉子點(diǎn)u2和強(qiáng)支撐點(diǎn)u3都相鄰的2度弱支撐點(diǎn),則一定存在一個(gè)γr3(T)-函數(shù)f使得f(u1)=?,f(u2)={1},f(u3)={1,2,3}且對(duì)任意與u3相鄰的葉子點(diǎn)x,f(x)=?.

γr3(T)≤ω(f)=

ω(h)+4-4=

ω(h)=

γr3(T)

因此ω(f)=γr3(T).意味著f也是一個(gè)γr3(T)-函數(shù).故f就是所求的γr3(T)-函數(shù).

引理4如果T=S1,t(t≥3)或T∈Π,則γgr3(T)-γr3(T)=2.

證明首先假設(shè)T=S1,t(t≥3).設(shè)v1和v2是雙星圖S1,t的支撐點(diǎn)且設(shè)N(v2){v1}={v3}.不難驗(yàn)證,函數(shù)f使得f(v1)={1,2,3},f(v3)={1}且當(dāng)x?{v1,v3}時(shí),f(x)=?是一個(gè)γr3(T)-函數(shù),并且函數(shù)h使得h(v1)=h(v2)={1,2,3}且當(dāng)x?{v1,v2}時(shí),h(x)=?是一個(gè)γgr3(T)-函數(shù).因此γgr3(T)-γr3(T)=2.

其次假設(shè)T∈Π.設(shè)v0是病態(tài)蜘蛛樹(shù)T∈Π的頭.令v1和v2是樹(shù)T的健康腳且對(duì)于任意i∈{1,2},令ui是與v0和vi都相鄰的弱支撐點(diǎn).不難驗(yàn)證,函數(shù)f使得f(v0)={1,2,3},f(v1)=f(v2)={1}且當(dāng)x?{v0,v1,v2}時(shí),f(x)=?是一個(gè)γr3(T)-函數(shù),并且函數(shù)h使得h(v0)=h(u1)={1,2,3},h(v2)={1}且當(dāng)x?{v0,u1,v2}時(shí),h(x)=?是一個(gè)γgr3(T)-函數(shù).因此γgr3(T)-γr3(T)=2.

命題1設(shè)P=v1v2…vk是樹(shù)T的一條最長(zhǎng)路且k≥4.若d(v2)≥3或d(vk-1)≥3,則γgr3(T)-γr3(T)≤2且等式成立當(dāng)且僅當(dāng)T=S1,t(t≥3).

證明首先給出以下斷言.

斷言1如果d(v2)=3或d(vk-1)=3,則γgr3(T)-γr3(T)≤1.

斷言1的證明不失一般性,假設(shè)d(v2)=3且設(shè)N(v2){v1,v3}={u}.令f是一個(gè)γr3(T)-函數(shù).注意到v2是度為3的強(qiáng)支撐點(diǎn),顯然有|f(v1)|+|f(v2)|+|f(u)|≥2.

若|f(v1)|+|f(v2)|+|f(u)|=2,則由γr3(T)-函數(shù)的定義知,f(v2)=?,|f(v1)|=|f(u)|=1且f(v1)∪f(wàn)(v3)∪f(wàn)(u)={1,2,3}.于是不妨設(shè)f(v1)={1},f(u)={2}且3∈f(v3).故不難看出函數(shù)h:V(T)→2{1,2,3}使得h(v2)={3}且當(dāng)x∈V(T){v2}時(shí),h(x)=f(x)是樹(shù)T的全局3-彩虹控制函數(shù).因此

γgr3(T)≤ω(h)=

ω(f)+|h(v2)|-|f(v2)|=

ω(f)+1=γr3(T)+1

若|f(v1)|+|f(v2)|+|f(u)|≥3,則定義樹(shù)T的一個(gè)全局3-彩虹控制函數(shù)h:V(T)→2{1,2,3}使得h(v1)={1},h(u)={2},h(v2)={3},h(v3)=f(v3)∪{3}且當(dāng)x∈V(T){v1,v2,v3,u}時(shí),h(x)=f(x).于是

γgr3(T)≤ω(h)=

ω(f)+(|h(u)|+|h(v1)|+

|h(v2)|)-(|f(u)|+|f(v1)|+

|f(v2)|)+(|h(v3)|-|f(v3)|)≤

ω(f)+3-3+(|f(v3)∪{3}|-

|f(v3)|)≤

ω(f)+1=

γr3(T)+1

斷言1得證.

斷言2如果k=4且d(v2)和d(vk-1)中至少有一個(gè)不小于4,則γgr3(T)-γr3(T)≤2且等式成立當(dāng)且僅當(dāng)T=S1,t(t≥3).

斷言2的證明不失一般性,假設(shè)d(v2)≥4.因?yàn)閗=4,所以樹(shù)T是雙星圖.如果d(v3)=2,則T=S1,t,其中t=d(v2)-1≥3,于是由引理4知,γgr3(T)-γr3(T)=2.如果d(v3)=3,則由斷言1知,γgr3(T)-γr3(T)≤1.如果d(v3)≥4,則函數(shù)f:V(T)→2{1,2,3}使得f(v2)=f(v3)={1,2,3}且當(dāng)x?{v2,v3}時(shí),f(x)=?既是一個(gè)γr3(T)-函數(shù)又是一個(gè)γgr3(T)-函數(shù),因此γgr3(T)=γr3(T).斷言2得證.

斷言3如果k≥5且d(v2)和d(vk-1)中至少有一個(gè)不小于4,則γgr3(T)-γr3(T)≤1.

斷言3的證明不失一般性,假設(shè)d(v2)≥4.注意到v2是至少與3個(gè)葉子點(diǎn)相鄰的強(qiáng)支撐點(diǎn),則由引理1,不妨設(shè)f是一個(gè)γr3(T)-函數(shù)使得f(v2)={1,2,3}且對(duì)任意x∈N(v2){v3},f(x)=?.

γgr3(T)≤ω(h)=

ω(f)+|h(v3)|-|f(v3)|=

ω(f)+|f(v3)∪{1}|-|f(v3)|≤

ω(f)+1=

γr3(T)+1

如果對(duì)任意u?N[v2],都有f(u)≠?成立,則函數(shù)h:V(T)→2{1,2,3}使得h(v3)=f(v3)∪{1},h(v4)={2},h(v5)={3}且當(dāng)x∈V(T){v3,v4,v5}時(shí),h(x)=f(x)是樹(shù)T的全局3-彩虹控制函數(shù),因此

γgr3(T)≤ω(h)=

ω(f)+(|h(v4)|+|h(v5)|)-

(|f(v4)|+|f(v5)|)+

(|h(v3)|-|f(v3)|)≤

ω(f)+2-2+(|f(v3)∪{1}|-

|f(v3)|)≤

ω(f)+1=

γr3(T)+1

斷言3得證.

由斷言1、2和3知,命題1成立.

命題2設(shè)P=v1v2…vk是樹(shù)T的一條最長(zhǎng)路且k≥4.若d(v2)=d(vk-1)=2,則γgr3(T)-γr3(T)≤2且等式成立當(dāng)且僅當(dāng)T∈Π.

證明如果k=4,則因?yàn)閐(v2)=d(v3)=2,所以T=v1v2v3v4是含有4個(gè)頂點(diǎn)的路,因此γgr3(T)=4=γr3(T).下面設(shè)k≥5.首先給出以下斷言.

斷言1如果N(v3){v2,v4}=?,則γgr3(T)-γr3(T)≤1.

γgr3(T)≤ω(h)=

ω(f)+3-2=

ω(f)+1=

γr3(T)+1

γgr3(T)≤ω(h)=

(|h(v4)|-|f(v4)|)≤

ω(f)+3-3+(|f(v4)∪{3}|-

|f(v4)|)≤

ω(f)+1=

γr3(T)+1

斷言1得證.

斷言2如果N(v3){v2,v4}中存在一個(gè)度至少為2的頂點(diǎn),則γgr3(T)-γr3(T)≤1.

斷言2的證明注意到k≥5.因?yàn)镻=v1v2…vk是樹(shù)T的一條最長(zhǎng)路且N(v3){v2,v4}中存在一個(gè)度至少為2的頂點(diǎn),所以N(v3){v2,v4}中一定含有樹(shù)T的強(qiáng)支撐點(diǎn)或弱支撐點(diǎn).如果N(v3){v2,v4}中存在一個(gè)強(qiáng)支撐點(diǎn),則因?yàn)閗≥5,所以類似于命題1中斷言1和3的證明可得,γgr3(T)-γr3(T)≤1.下面假設(shè)N(v3){v2,v4}中存在一個(gè)弱支撐點(diǎn),不妨設(shè)為u1.令N(u1){v3}={u2}.由于d(v1)=d(u2)=1且d(v2)=d(u1)=2,則由引理2,不妨設(shè)f是一個(gè)γr3(T)-函數(shù)使得f(v1)=f(u2)={1},f(v2)=f(u1)=?且{2,3}?f(v3).

如果k=5,則因?yàn)閐(v4)=2,d(v5)=1且{2,3}?f(v3),所以由γr3(T)-函數(shù)的定義知,f(v4)=?且|f(v5)|=1,不妨設(shè)f(v5)={1};如果k≥6且f(vk-1)和f(vk)都不為?,則因?yàn)閐(vk)=1,所以由γr3(T)-函數(shù)的定義知,|f(vk)|=1,不妨設(shè)f(vk)={1}.于是這兩種情況下,不難看出函數(shù)h:V(T)→2{1,2,3}使得h(v1)={2},h(v2)={3}且當(dāng)x?{v1,v2}時(shí),h(x)=f(x)是樹(shù)T的全局3-彩虹控制函數(shù).因此

γgr3(T)≤ω(h)=

ω(f)+(|h(v1)|+|h(v2)|)-

(|f(v1)|+|f(v2)|)=

ω(f)+2-1=

γr3(T)+1

下面考慮最后一種情況,即k≥6且f(vk-1)和f(vk)中至少有一個(gè)為?.注意到由γr3(T)-函數(shù)的定義知,若f(vk-1)=?,則f(vk-2)∪f(wàn)(vk)={1,2,3};若f(vk)=?,則f(vk-1)={1,2,3}.于是不難驗(yàn)證函數(shù)h:V(T)→2{1,2,3}使得h(v4)=f(v4)∪{1}且當(dāng)x∈V(T){v4}時(shí),h(x)=f(x)是樹(shù)T的全局3-彩虹控制函數(shù).因此

γgr3(T)≤ω(h)=

ω(f)+|h(v4)|-|f(v4)|=

ω(f)+|f(v4)∪{1}|-|f(v4)|≤

ω(f)+1=

γr3(T)+1

斷言2得證.

斷言3如果|N(v3){v2,v4}|=1且N(v3){v2,v4}中的頂點(diǎn)為葉子點(diǎn),則γgr3(T)-γr3(T)≤1.

斷言3的證明設(shè)N(v3){v2,v4}={u}且設(shè)f是一個(gè)γr3(T)-函數(shù).由于d(v1)=d(u)=1,則顯然有

|f(v1)|+|f(v2)|≥1且|f(v3)|+|f(u)|≥1

(1)

γgr3(T)≤ω(h)=

ω(f)+4-3=

γr3(T)+1

γgr3(T)≤ω(h)=

(|h(v4)|-|f(v4)|)≤

ω(f)+4-4+(|f(v4)∪{3}|-

|f(v4)|)≤

ω(f)+1=

γr3(T)+1

斷言3得證.

斷言4如果|N(v3){v2,v4}|≥2且N(v3){v2,v4}中的頂點(diǎn)都為葉子點(diǎn),則γgr3(T)-γr3(T)≤2且等式成立當(dāng)且僅當(dāng)T∈Π.

斷言4的證明注意到k≥5.首先假設(shè)k=5.若|N(v3){v2,v4}|=2,則不妨設(shè)N(v3){v2,v4}={u1,u2}.又因?yàn)閐(v2)=d(v4)=2,所以V(T)={v1,v2,v3,v4,v5,u1,u2}.于是函數(shù)f使得f(v1)=f(v5)={1},f(v3)={1,2,3}且當(dāng)x?{v1,v3,v5}時(shí),f(x)=?是一個(gè)γr3(T)-函數(shù),并且函數(shù)h使得h(v1)=h(v5)={1},h(v2)=h(v4)=?,h(v3)={2,3},h(u1)={2}且h(u2)={3}是一個(gè)γgr3(T)-函數(shù).因此γgr3(T)-γr3(T)=6-5=1.若|N(v3){v2,v4}|≥3,則T∈Π,于是由引理4知,γgr3(T)-γr3(T)=2.

其次假設(shè)k≥6.如果N(vk-2){vk-3,vk-1}=?,則類似于斷言1的證明可得γgr3(T)-γr3(T)≤1.如果N(vk-2){vk-3,vk-1}中存在度至少為2的頂點(diǎn),則類似于斷言2的證明可得γgr3(T)-γr3(T)≤1.如果|N(vk-2){vk-3,vk-1}|=1且N(vk-2){vk-3,vk-1}中的頂點(diǎn)為葉子點(diǎn),則類似于斷言3的證明可得γgr3(T)-γr3(T)≤1.下設(shè)|N(vk-2){vk-3,vk-1}|≥2且N(vk-2){vk-3,vk-1}中的頂點(diǎn)都為葉子點(diǎn).

由于N(v2)={v1,v3}且v1和v3分別是葉子點(diǎn)和強(qiáng)支撐點(diǎn),則由引理3,不妨設(shè)f是一個(gè)γr3(T)-函數(shù)使得f(v1)={1},f(v2)=?,f(v3)={1,2,3}且對(duì)任意x∈N(v3){v2,v4},f(x)=?.由于d(vk-1)=2,d(vk)=1且vk-2是強(qiáng)支撐點(diǎn),則再次由引理3,不妨設(shè)f(vk)={1},f(vk-1)=?,f(vk-2)={1,2,3}且對(duì)任意x∈N(vk-2){vk-3,vk-1},f(x)=?.于是不難看出函數(shù)h:V(T)→2{1,2,3}使得h(v1)={2},h(v2)={3}且當(dāng)x?{v1,v2}時(shí),h(x)=f(x)是樹(shù)T的全局3-彩虹控制函數(shù),因此

γgr3(T)≤ω(h)=

ω(f)+(|h(v1)|+|h(v2)|)-

(|f(v1)|+|f(v2)|)=

ω(f)+2-1=

γr3(T)+1

斷言4得證.

由斷言1～4可知,命題2成立.

定理1對(duì)任意樹(shù)T,下列結(jié)論成立:

(1)γgr3(T)-γr3(T)=2當(dāng)且僅當(dāng)T∈{K1,4,S1,t(t≥3)}∪Π.

(2)γgr3(T)-γr3(T)=3當(dāng)且僅當(dāng)T=K1,n-1(n≥6).

證明設(shè)樹(shù)T含有n個(gè)頂點(diǎn).如果n≤3,則易見(jiàn)γgr3(T)=n=γr3(T).下面設(shè)n≥4.如果樹(shù)T的直徑為2,即T=K1,n-1,則當(dāng)n=4時(shí),γgr3(T)-γr3(T)=4-3=1;當(dāng)n=5時(shí),γgr3(T)-γr3(T)=5-3=2;當(dāng)n≥6時(shí),γgr3(T)-γr3(T)=6-3=3.如果樹(shù)T的直徑至少為3,則由命題1和2知,γgr3(T)-γr3(T)≤2且等式成立當(dāng)且僅當(dāng)T=S1,t(t≥3)或T∈Π.定理1得證.

3 結(jié) 語(yǔ)

本文研究了圖的經(jīng)典控制數(shù)的一個(gè)衍生控制參數(shù),即全局彩虹控制數(shù)問(wèn)題.通過(guò)對(duì)樹(shù)的結(jié)構(gòu)分析,刻畫了γgr3(T)-γr3(T)=2和γgr3(T)-γr3(T)=3成立的所有樹(shù)T,推廣了已知結(jié)果.期望在今后的研究工作中能夠進(jìn)一步刻畫γgr3(T)-γr3(T)=1成立的所有樹(shù)T.