兩類特殊Corona圖的b-染色數與b-連續性

代天驕，姚 兵

(1.山東大學數學學院，山東 濟南 250100； 2.西北師范大學數學與統計學院，甘肅 蘭州，730070)

兩類特殊Corona圖的b-染色數與b-連續性

代天驕1，姚 兵2

(1.山東大學數學學院，山東 濟南 250100； 2.西北師范大學數學與統計學院，甘肅 蘭州，730070)

構造了兩個特殊模型：路圖(圈)與完全圖中去掉一個匹配所構成圖的Corona圖.研究了這兩個特殊Corona圖的m-度與b-染色數，并證明了它們是b-連續的.

m-度；b-染色；b-染色數；b-連續；Corona圖；完全圖；完美匹配

1999年，Irving等[1]在圖的a-染色基礎上提出了圖的b-染色：在一個圖G的正常k染色中，如果每一個顏色類中都至少存在一個頂點，使得在其他的k-1個顏色類中都至少存在一個鄰點，則稱這樣的正常k染色為b-染色.一個圖G的b-染色數為最大的正整數k，如果用k種顏色能夠對G進行b-染色，并記為b(G).同時其給出了b-染色數的一個上界m(G)，即圖G的m-度，并證明了確定一個一般圖G的b-染色數b(G)是一個NP-完全問題，同時求得了樹圖的b-染色數.從此，有關b-染色的問題便引起了眾多學者的關注.

Effantin和Kheddouci[2-4]研究了路、圈以及完全二元樹圖和完全毛毛蟲圖的b-染色數.2004年，Faik[5]又證明了弦圖是b-連續的.2012年，Vernold等[6]證明了對于任意含有n個頂點的兩個圖G1與G2，Corona圖G=G1°G2是可b-染色的，且研究并證明了G1與G2在不同情形下的Corona圖G=G1°G2的b-染色數.該文還提出了對于任意具有n個頂點的兩個圖G1與G2的Corona圖G=G1°G2，或特殊的Corona圖G=G1°G2可能是b-連續和b-單調的.

在文獻[6]的啟發下，本文研究了兩類特殊的模型：路圖或圈圖與在完全圖中去掉一個匹配所構成圖的Corona圖.研究了這兩類特殊Corona圖的m-度與b-染色數，并證明了它們是b-連續的.

1 預備知識

本文涉及的圖均為簡單、無向的有限圖.

定義1.2[1]在一個圖G的正常k染色中，如果每一個顏色類中都至少存在一個頂點，使得在其他的k1個顏色類中都至少存在一個鄰點，則稱這樣的正常k染色為b-染色，這樣的頂點稱為b-染色頂點.一個圖G的b-染色數為最大的正整數k，使得用k種顏色能夠對G進行b-染色，并用b(G)表示.

n階完全圖是指n階的簡單圖，且任意兩個不同的頂點都有邊相連.設圖G=(V，E)的頂點v1，v2，…，vn按照頂點的度降序排列，即d(v1)≥d(v2)≥…≥d(vn)，圖G的m-度定義為

m(G)=max{i|d(vi)≥i-1，1≤i≤n}.[1]

圖G的邊子集M稱為圖G的一個匹配，如果M中的任意兩條邊互不相鄰.若G的每個頂點是M中一條邊的端點，則稱匹配M飽和G的每個頂點，稱匹配M是圖G的一個完美匹配.

對于圖G1與G2，稱圖G=G1°G2為圖G1與G2的Corona圖，如果G包含G1的一個拷貝，包含了G2的|V(G1)|個拷貝，且G1的第i個頂點與G2的第i個拷貝的所有頂點都鄰接.[6]

引理1.1[1]設G是任意圖，則b(G)≤m(G).

2 主要結論及證明

引理2.1 設n為任意正整數，Pn為含有n個頂點的路圖，K2n為含有2n個頂點的完全圖，M為K2n的一個完美匹配.則

m[Pn°(K2n-M)]=2n.

證明設路Pn的頂點集為V(Pn)={v1，v2，…，vn}，其中

d(v1)=d(vn)=1，d(v2)=d(v3)=…=d(vn-1)=2.

設K2n-M的頂點集為

V(K2n-M)={u1，u2，…，u2n}，

從而Corona圖Pn°(K2n-M)的頂點集可表示為

V(Pn°(K2n-M))={vi|1≤i≤n}∪{uij|1≤i≤n，1≤j≤2n}.

由Corona圖的定義可知，對于任意的頂點vi∈V(Pn°(K2n-M))，vi與集合{uij|1≤j≤2n}中的任意頂點都是鄰接的.在圖Pn°(K2n-M)中，有n個度不小于2n+1的頂點，有2n2個度為2n-1的頂點，即

d(v1)=d(vn)=2n+1，d(v2)=d(v3)=…=d(vn-1)=2n+2，d(uij)=2n-1.

故由圖的m-度定義可知

m[Pn°(K2n-M)]=2n.

定理2.1 設n為任意正整數，Pn為含有n個頂點的路圖，K2n為含有2n個頂點的完全圖，M為K2n的一個完美匹配.則有

b[Pn°(K2n-M)]=m[Pn°(K2n-M)]=2n，

且Pn°(K2n-M)是b-連續的.

證明設路Pn的頂點集為

V(Pn)={v1，v2，…，vn}，

其中

d(v1)=d(vn)=1，d(v2)=d(v3)=…=d(vn-1)=2.

設K2n-M的頂點集為

V(K2n-M)={u1，u2，…，u2n}，

從而Corona圖Pn°(K2n-M)的頂點集可表示為

V(Pn°(K2n-M))={vi|1≤i≤n}∪{uij|1≤i≤n，1≤j≤m}.

(1) 對Corona圖G=Pn°(K2n-M)中的n個頂點v1，v2，…，vn用顏色1，2，…，n進行染色.

(2) 對于與任意頂點vi(1≤i≤n)相鄰的2n個頂點ui1，ui2，…，ui2n進行染色.將圖K2n-M中的2n個頂點按照頂點的對稱性分成兩部分：A={ui1，ui2，…，ui(n-1)，uin}與B={ui(2n)，ui(2n-1)，…，ui(n+1)}.其次，對于A中的n個頂點，對ui2用第n+i色進行染色，其他n-1個頂點用[1，n]{i}里的顏色依次進行染色；對于B中的n個頂點，在M中與ui2相鄰的頂點ui(2+n+1)用第n+i色進行染色，其他n-1個頂點中，有a-1個頂點分別用第{n+1，n+2，…，n+a}{n+i}顏色進行染色，余下的n-a個頂點分別按照在原K2n中構成完美匹配且被去掉的那個匹配所對應的端點染相同顏色.采用通用b-染色方案，用k種顏色就可以對Corona圖G=Pn°(K2n-M)實現b-染色，結論得證.

綜上所述，對于任意的正整數n，Corona圖Pn°(K2n-M)是b-連續的，有

b[Pn°(K2n-M)]=m[Pn°(K2n-M)]=2n.

引理2.2 設Cn為含有n個頂點的圈圖，K2n為含有2n個頂點的完全圖，M為K2n的一個完美匹配.則

m[Cn°(K2n-M)]=2n.

證明設圈Cn的頂點集為

V(Cn)={v1，v2，…，vn}，

其中

d(v1)=d(v2)=…=d(vn-1)=d(vn)=2.

設K2n-M的頂點集為

V(K2n-M)={u1，u2，…，u2n}，

從而Corona圖Cn°(K2n-M)的頂點集可表示為

V(Cn°(K2n-M))={vi|1≤i≤n}∪{uij|1≤i≤n，1≤j≤m}.

由Corona圖的定義，對于任意頂點vi∈V(Cn°(K2n-M))，vi與集合{uij|1≤j≤m}中的任意頂點都是相鄰的.在圖Cn°(K2n-M)中，有n個度為2n+2的頂點，有2n個度為2n-1的頂點，即

d(v1)=d(v2)=…=d(vn)=2n+2，d(uij)=2n-1，

從而由m-度的定義得m[Cn°(K2n-M)]=2n.

定理2.2 設n為任意正整數，Cn為含有n個頂點的圈圖，K2n為含有2n個頂點的完全圖，M為K2n的一個完美匹配.則

b[Cn°(K2n-M)]=m[Cn°(K2n-M)]=2n，

且Cn°(K2n-M)是b-連續的.

證明設圈Cn的頂點集為

V(Cn)={v1，v2，…，vn}，

其中

d(v1)=d(v2)=…=d(vn-1)=d(vn)=2.

設K2n-M的頂點集為

V(K2n-M)={u1，u2，…，u2n}，

從而Corona圖Cn°(K2n-M)的頂點集可表示為

V(Cn°(K2n-M))={vi|1≤i≤n}∪{uij|1≤i≤n，1≤j≤m}.

(1) 對Corona圖G=Cn°(K2n-M)中的n個頂點v1，v2，…，vn用顏色1，2，…，n進行染色.

(2) 對于與任意頂點vi(1≤i≤n)相鄰的2n個頂點ui1，ui2，…，ui2n進行染色.將圖K2n-M中的2n個頂點按照頂點的對稱性分成兩部分：A={ui1，ui2，…，ui(n-1)，uin}與B={ui(2n)，ui(2n-1)，…，ui(n+1)}.前一部分A中的n個頂點用第n+i色對每個ui2進行染色，其他n-1個頂點用[1，n]{i}里的顏色依次進行染色.對于B中的n個頂點，在M中與ui2相鄰的頂點ui(2+n+1)用第n+i色進行染色；其他n-1個頂點中，有a-1個頂點分別用第{n+1，n+2，…，n+a}{n+i}顏色進行染色，余下的n-a個頂點分別按照在原K2n中構成完美匹配且被去掉的匹配所對應的端點染相同顏色.采用通用b-染色方案，用k種顏色就可以對Corona圖G=Cn°(K2n-M)實現b-染色.

綜上所述，對于任意的正整數n，Corona圖Cn°(K2n-M)是b-連續的，且

b[Cn°(K2n-M)]=m[Cn°(K2n-M)]=2n.

3 結束語

在Vernold等工作的啟發下，構造了兩類特殊的模型：路圖(圈)與完全圖中去掉一個匹配所構成圖的Corona圖，研究了這兩類特殊Corona圖的m-度與b-染色數，并證明其皆是b-連續的.接下來，將重點研究對于更為一般的兩個圖G1與G2所構成的Corona圖G1°G2的b-染色數與b-連續性，以期得到較為深刻和廣泛的結果.

[1] IRVING R W，MANLOVE D F.Theb-chromatic number of a graph[J].Discrete Applied Mathematics，1999，91(1/2/3)：127-141.

[2] EFFANTIN B.Theb-chromatic number of power graphs of complete caterpillars[J].Discrete Math Science & Cryptograph，2005，8(3)：483-502.

[3] EFFANTIN B，KHEDDOUCI H.Theb-chromatic number of some power graphs[J].Discrete Math Theor Comput Sci，2003，6(1)：45-64.

[4] EFFANTIN B，KHEDDOUCI H.Exact values for theb-chromatic number of a power completek-arytree[J].Discrete Math Sci Cryptogr，2005，8：117-129.

[5] FAIK T.About theb-continuity of graphs[J].Electronic Notes in Discrete Mathematics，2004，17：151-156.

[6] VERNOLD V J，VENKATACHALAM M.Theb-chromatic number of Corona graphs[J].Utilitas Mathematica，2012，88：299-307.

[7] 迪斯特爾 R.圖論[M].于青林，王濤，王光輝，等譯.第4版.北京：高等教育出版社，2013：108-109.

(責任編輯：李亞軍)

Theb-chromaticnumberandb-continuityofthetwotypesofspecialCoronagraphs

DAI Tian-jiao1，YAO Bing2

(1.School of Mathematics，Shandong University，Jinan 250100，China； 2.College of Mathematics and Statistics，Northwest Normal University，Lanzhou 730070，China)

The two types of special Corona graphs are researched.Them-degree andb-chromatic number of these graphs are studied.Theb-continuity of these graphs is given.

m-degree；b-coloring；b-chromatic number；b-continuous；Corona graph；complete graph；perfect matching

1000-1832(2017)03-0034-04

10.16163/j.cnki.22-1123/n.2017.03.008

2015-12-31

國家自然科學基金資助項目( 61163054，61363060，61662066).

代天驕(1995—)，女，碩士，主要從事圖著色與標號以及復雜網絡研究；通信作者：姚兵(1956—)，男，教授，主要從事圖著色與標號以及復雜網絡研究.

O 211.2 [學科代碼] 110·7470

A