梁冰冰，皮曉明，劉煥平

（哈爾濱師范大學數(shù)學系，黑龍江 哈爾濱 150025）

樹的3-彩虹控制數(shù)的上界

梁冰冰，皮曉明，劉煥平

（哈爾濱師范大學數(shù)學系，黑龍江 哈爾濱 150025）

對樹的3-彩虹控制數(shù)進行研究，首先用構造法找到直徑較小的樹的3-彩虹控制數(shù)的上界.再通過分類討論思想和數(shù)學歸納法得到一般的階n大于等于5的樹的3-彩虹控制數(shù)的上界.

樹；控制數(shù)；彩虹控制數(shù)

DO I：10.3969/j.issn.1008-5513.2015.02.012

1 引言

1962年，文獻［1］首先給出了控制數(shù)的數(shù)學定義.同時，隨著科學技術的進步和實際問題的發(fā)展，國內外許多學者開始研究各種類型的控制函數(shù).2005年，文獻［2］提出了彩虹控制數(shù)的概念.在以后的幾年里，一些數(shù)學家陸續(xù)給出了有關彩虹控制數(shù)的相關結論.文獻［3］證明了對于任意的正整數(shù)k，圖的k-彩虹控制數(shù)是一個NP完全問題.這說明對于圖的k-彩虹控制數(shù)的研究是非常困難的.文獻［4］給出路和圈的2-彩虹控制數(shù)以及Petersen圖的2-彩虹控制數(shù)的上界.在這基礎上，文獻［5］給出樹的2-彩虹控制數(shù)的關于頂點個數(shù)的上界和關于最大頂點度的下界，還給出了一般連通圖的2-彩虹控制數(shù)的關于直徑的上界和下界.2014年，文獻［6］得到了路、圈、Petersen圖的3-彩虹控制數(shù)以及一般連通圖的3-彩虹控制數(shù)的上界.特別地，得到

引理1.1［6］若 n≥5，則

2 預備知識

本文中的圖G都是連通的無向簡單圖.V（G）表示圖G的頂點集，E（G）表示圖G的邊集.設S?V（G）,稱

給定一個圖G和正整數(shù)k，圖G的k-彩虹控制函數(shù)f是指滿足下列條件的映射f：V（G）→2｛1，2，··，k｝，使得若頂點v滿足f（v）=?，則

是k-彩虹控制函數(shù)f的權.圖G的k-彩虹控制數(shù)γrk（G）=m in｛ω（f）|f是G的k-彩虹控制函數(shù)｝.G的具有權γrk（G）的k-彩虹控制函數(shù)稱為最小k-彩虹控制函數(shù).與一個一度點相鄰的點稱為支撐點，與一度點相關聯(lián)的邊稱為懸掛邊.邊的n度細分是從圖G中刪去一條邊uv，并用一條與G中點內部不交的長為n+1的路連接u，v.邊的樹枝化是把G的一條邊一度細分后變成uwv，在w處附著一條懸掛邊.邊的星化是把G的一條邊一度細分后變成uwv，在w處附著至少兩條懸掛邊，w稱為星化點.

圖1 A，B，C三種子圖

樹枝型圖是把星圖的至少一條邊星化，樹枝化或一度細分得到的非路的圖；星圖的中心稱為樹枝型圖的中心，度大于等于4的非中心的支撐點稱為樹枝型圖的次中心.伸長型圖是在樹枝型圖或星圖的中心u處至少附著圖b、圖c兩種子圖之一的非路的圖；樹枝型圖或星圖的中心稱為伸長型圖的中心，樹枝型圖的次中心稱為伸長型圖的次中心.手指型圖G是在星圖K1，m的一些邊上最多2度細分后得到的圖G′上，添加頂點集V′和邊集E′使每一頂點v∈V′恰與V（G′）?V（K1，m）的一個頂點相鄰，在此基礎上，再在K1，m的中心u處附著至少一個圖1中A型子圖得到的非路的圖；星圖的中心u稱為手指型圖的中心.

3 主要結果及證明

對星圖顯然有下面結論成立：

定理3.1 若G是階n≥4的星圖，則γr3（G）=3.

圖2 a=0，b=c=d=1

證明 設 G是在星圖 K1，m中分別星化，樹枝化和一度細分 a,b,c條邊后得到的圖，令d=m?a?b?c，u是G的中心，則n≥4a+3b+2c+d+1且a+b+c≥1.令X=｛x∈V（G）|x是G的次中心｝，接下來分以下情形討論.

情形1 d≥3或d=2且b+c≥1.令

則 F是G的一個3-彩虹控制函數(shù)，且ω（F）=3a+2b+c+3，于是

情形2 d=2且b+c=0或d≤1,a=c=1,b=0.令

則F是G的一個3-彩虹控制函數(shù)，且ω（F）=3a+2c+d，于是

則F是G的一個3-彩虹控制函數(shù)，且ω（F）=3a+2b+c+d+2，于是

若兩個不等式等號同時成立，則γr3（G）=ω（F）,n=4a+3b+2c+d+1且

綜上所述，當且僅當G是圖2所示的圖時，上述兩個不等式的等號同時成立.

情形4 d≤1,c=0.令

對于任意的v∈N，令

其中p1（v）,p2（v）是v的兩個一度鄰點.對于其他的點v∈V（G）?N1，令

則F是G的一個3-彩虹控制函數(shù)，且ω（F）=3a+2b+d+1，于是

圖3 a=c=e=0，b=d=f=1

證明 設G′是在星圖K1，m中分別星化，樹枝化和一度細分a,c,e條邊得到的樹枝型圖，則G是通過在G′的中心或星圖的中心u處分別附著b個B型子圖和d個C型子圖得到的伸長型圖.令f=m?a?c?e，則n≥4（a+b）+3（c+d）+2e+f+1且b+d≥1.接下來分以下情形討論.令X=｛x∈V（G）|x是G的次中心｝.

情形1 f≥2.令

則F是G的一個3-彩虹控制函數(shù)，且ω（F）=3（a+b）+2（c+d）+e+3，于是

情形2 f≤1,d+e≥1.令

則F是G的一個3-彩虹控制函數(shù)，且ω（F）=3（a+b）+2（c+d）+e+f+2，于是

若兩個不等式等號同時成立，則

綜上所述，當且僅當G是圖3所示的圖時，兩個不等式的等號同時成立.

對于任意v∈N，令F（p1（v））=｛2｝,F（p2（v））=｛3｝，其中p1（v）,p2（v）是v的兩個非中心的鄰點.對于其他的點v∈V（G）?N1，令

則F是G的一個3-彩虹控制函數(shù)，且ω（F）=3（a+b）+2c+f+1，于是

證明 對于手指型圖G，刪除G的中心u后得到一些子圖，把這些子圖中的階大于等于5的樹枝型圖和階大于等于4的星圖的并記為G1，則由引理3.1和定理3.1知

于是 G2=G?G1只包含圖 4中的6種子圖，記 G2包含以下6種子圖的個數(shù)依次為a,b,c,d,e,f，

圖4 G2的幾種子圖

則|V（G2）|=n2=4（a+b）+3（c+d）+2e+f+1且a≥1.接下來分以下情形討論.

情形1 f≥2.令

則F2是G2的一個3-彩虹控制函數(shù)，且ω（F2）=3（a+b）+2（c+d）+e+3，于是

情形2 f≤1,e+c≥1.令

則F2是G2的一個3-彩虹控制函數(shù)，且ω（F2）=3（a+b）+2（c+d）+e+f+2,于是

若不等式等號成立，則

且結合情形2的條件及a≥1得，只能是a=c=f=1,b=d=e=0（如圖5）.反過來，設G2是圖4所示的圖，則G2中除中心u外所有點的度均小于等于2.假設G2的3-彩虹控制數(shù)不超過7且是G2的最小3-彩虹控制函數(shù)，則必有而其余點在下的值都是一元集，其中v是G2中一個不同于u的頂點，這是不可能的.所以G2的3-彩虹控制數(shù)大于等于8.從而設G是n（≥5）階的3-彩虹控制數(shù)為的手指型圖，則由引理3.2及上述證明知，G=G2或G是通過在圖3和圖5的中心之間連邊得到的圖，但后者顯然不是手指型圖，所以G=G2.于是當且僅當G是圖5所示的圖時，不等式的等號成立.

圖5 a=c=f=1，b=d=e=0

對于任意v∈N，令F（p1（v））=｛2｝,F（p2（v））=｛3｝，其中p1（v）,p2（v）是v的兩個非中心的鄰點.對于其他的點v∈V（G2）?N1，令

其中A是手指型圖G的中心u處附著的圖1中的A型子圖，則F2是G2的一個3-彩虹控制函數(shù)，且ω（F2）=3（a+b）+2d+f+1，于是

設F1是G1的最小3-彩虹控制函數(shù)，定義

則F是G的一個3-彩虹控制函數(shù)，且

證明 用歸納法進行證明，先考慮一些直徑較小的樹.

情形2 3≤diam（T）≤4.則T是一個n≥5的路或樹枝型圖，由引理1.1及推論3.1知，結論成立.

情形 3.1 n1≤4,n2≤4.顯然T1或T2中每個頂點的度均不大于3，且T中至少有一個點h的度等于3，令F（h）=｛1,2,3｝,

當T2不是一個n2=4的星圖時，T是一個以u1為中心的伸長型圖，由推論1知，結論成立.

結論成立.

情形 4 6≤diam（T）≤8.選取T的最長路P，使與P的端點相鄰的支撐點v的度最大，令v,u,t,x分別是P上依次相鄰的頂點，分以下情形討論.

情形4.2 dT（v）=3且dT（u）＞2.設T?ut的兩個連通分支為樹T1,T2，令含v的分支為T1，顯然T1的階至少為5，通過與情形4.1類似的討論得結論成立.

情形 4.3 dT（v）=2.當dT（u）＞3時，通過與情形4.2類似的討論知結論成立.下設dT（u）≤3.

情形 4.3.1 dT（u）=3.若u不是支撐點，通過與情形4.2類似的討論知結論成立.設u是支撐點，且T?tx的兩個分支是階分別為n1和n2的樹T1和T2，令含t的分支為T1，顯然n1≥5.當n2≥5時，由歸納假設，易證結論成立.設n2≤4，則diam（T）≤7.

情形4.3.1.1 dT（t）=2.當diam（T）=6時，若T中除u外的所有頂點的度都小于3，則n=8，令F（u）=｛1,2,3｝,對任意的v∈NT（u）,F（v）=?，對任意的

情形4.3.1.2 dT（t）＞2.當diam（T）=6時，由前面的討論和v的選取及x與u的對稱性知，只需討論dT（x）=2或dT（x）=3且x是支撐點的情形.無論是前者還是后者，T都是一個以t為中心的伸長型圖.當diam（T）=7時，T是一個以t為中心的手指型圖，由推論3.1知，結論成立.

情形4.3.2 dT（u）=2.由v的選取及前面的討論知，P上與P的另一端點相鄰的點和與之距離為2的點的度均為2，于是只需討論P上與P的另一端點距離為3和4的點的度的情形.

情形 4.3.2.1 dT（t）＞2.T?tx把T分為階分別是n1和n2的樹T1和T2.令含t的樹為T1，則n1≥5.當n2≥5時，由歸納假設易證結論成立；否則diam（T）≤7，此時，T是一個以t為中心的伸長型圖或手指型圖，由推論3.1知，結論成立.

情形 4.3.2.2 dT（t）=2.當diam（T）=6或7時，T為n=7或8的路，由引理1.1知，結論成立.當diam（T）=8時，若dT（x）=2，T是n=9的路，由引理1.1知，結論成立.若dT（x）≥2，T是一個手指型圖，由推論3.1知，結論成立.

則F是T的一個3-彩虹控制函數(shù)，于是

［1］Ore O.Theory of Graphs［M］.USA：Amer.Math.Soc.Colloq.Publ.，1962.

［2］Bre?sar B，Henning M A，Rall D F.Paired-dom ination of Cartesian products of graphs and rainbow dom ination［J］.Electron.Notes Discrete Math.，2005，22：233-237.

［3］Chang C J，W u J J，Zhu X D.Rainbow dom ination on trees［J］.Discrete App l.M ath.，2010，158：8-12.

［4］Bre?sar B，Sumenjak T K.On the 2-rainbow dom ination in graphs［J］.Discrete App l.M ath.，2007，155：2394-2400.

［5］Wu Y J，Rad N J.Bounds on the 2-rainbow dom ination number of graphs［J］.G raphs Combin.，2013，29：1125-1133.

［6］Shao ZH，Liang M L，Yin C，et al.On rainbow dom ination numbers ofgraphs［J］.Inf.Sci.，2014，254：225-234.

2010 M SC：05C69

U pper bounds on the 3-rainbow dom ination num ber o f trees

Liang Bingbing，Pi Xiaom ing，Liu Huanping
（School of M athem atical Sciences，Harbin Norm al University，Harbin 150025，China）

This paper studies 3-rainbow dom ination number of trees.First we give an upper bound for the 3-rainbow dom ination number of treesw ith small Geter by the construction method.Second，we give an upper bound on the 3-rainbow dom ination number of trees w ith order n equaling or greater than 5 by induction and the idea of classif cation discussion.

tree，dom ination number，rainbow dom ination number

O157.5

A

1008-5513（2015）02-0210-11

2017-04-02.

黑龍江省教育廳科學技術研究項目（12531203；12521148）；哈爾濱師范大學青年學術骨干項目基金（10XBKQ 08）.

梁冰冰（1989-），碩士生，研究方向：組合數(shù)學與圖論.

皮曉明（1977-），副教授，碩士生導師，研究方向：圖論與組合最優(yōu)化.