兩類特殊Corona圖的b-染色數(shù)與b-連續(xù)性

代天驕，姚 兵

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

兩類特殊Corona圖的b-染色數(shù)與b-連續(xù)性

代天驕1，姚 兵2

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

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

m-度；b-染色；b-染色數(shù)；b-連續(xù)；Corona圖；完全圖；完美匹配

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

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

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

1 預(yù)備知識

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

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

n階完全圖是指n階的簡單圖，且任意兩個不同的頂點都有邊相連.設(shè)圖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]設(shè)G是任意圖，則b(G)≤m(G).

2 主要結(jié)論及證明

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

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

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

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

設(shè)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 設(shè)n為任意正整數(shù)，Pn為含有n個頂點的路圖，K2n為含有2n個頂點的完全圖，M為K2n的一個完美匹配.則有

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

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

證明設(shè)路Pn的頂點集為

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

其中

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

設(shè)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中構(gòu)成完美匹配且被去掉的那個匹配所對應(yīng)的端點染相同顏色.采用通用b-染色方案，用k種顏色就可以對Corona圖G=Pn°(K2n-M)實現(xiàn)b-染色，結(jié)論得證.

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

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

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

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

證明設(shè)圈Cn的頂點集為

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

其中

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

設(shè)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 設(shè)n為任意正整數(shù)，Cn為含有n個頂點的圈圖，K2n為含有2n個頂點的完全圖，M為K2n的一個完美匹配.則

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

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

證明設(shè)圈Cn的頂點集為

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

其中

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

設(shè)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中構(gòu)成完美匹配且被去掉的匹配所對應(yīng)的端點染相同顏色.采用通用b-染色方案，用k種顏色就可以對Corona圖G=Cn°(K2n-M)實現(xiàn)b-染色.

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

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

3 結(jié)束語

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

[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—)，女，碩士，主要從事圖著色與標號以及復(fù)雜網(wǎng)絡(luò)研究；通信作者：姚兵(1956—)，男，教授，主要從事圖著色與標號以及復(fù)雜網(wǎng)絡(luò)研究.

O 211.2 [學科代碼] 110·7470

A