mC6的點(diǎn)可區(qū)別全染色*

何玉萍，王治文，陳祥恩

(1. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070；2. 寧夏大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，寧夏 銀川 750021)

隨著圖的染色問題在現(xiàn)實(shí)生活中的廣泛應(yīng)用，它逐漸地成為被許多學(xué)者研究的重要領(lǐng)域之一。起源于網(wǎng)絡(luò)問題，生物，信息科學(xué)，計(jì)算機(jī)科學(xué)，點(diǎn)可區(qū)別正常邊染色和點(diǎn)可區(qū)別正常全染色問題是有趣和困難的問題。文獻(xiàn)[1-3]探討了圖的點(diǎn)可區(qū)別正常邊染色。本文研究一類圖的點(diǎn)可區(qū)別正常全染色。

設(shè)f:V∪E→{1,2,…,k}為G=(V,E)的一個(gè)正常全染色。任意的v∈V, 將與v關(guān)聯(lián)的邊的色以及v的顏色組成的集合，稱作v的色集合或調(diào)色板，記為Cf(v)或C(v)，即C(v)={f(vw)|vw∈E}∪{f(v)}。

若任意的u,v∈V，有C(u)≠C(v),dG(u,v)=diam(G)，則稱f為G的點(diǎn)可區(qū)別全染色(簡稱為VDTC)。 若G的點(diǎn)可區(qū)別全染色使用了k種顏色, 則稱f為G的k-點(diǎn)可區(qū)別全染色(簡稱為k-VDTC)。

對(duì)于圖G，用ni(G)表示圖G的度為i的頂點(diǎn)個(gè)數(shù), 且記

顯然有χvt(G) ≥μ(G)。

張忠輔等[4]首次提出圖的點(diǎn)可區(qū)別(正常)全染色，并且確定了完全圖, 完全二部圖, 輪, 扇, 雙星, 路, 圈, 兩條同階路的聯(lián)圖,n階路與n圈的聯(lián)圖, 兩條同階圈的聯(lián)圖等圖類的點(diǎn)可區(qū)別全染色數(shù), 并提出了下面的猜想。

VDTC猜想χvt(G) =μ(G) 或μ(G)+1。

文獻(xiàn)[5-8]給出了mK4,mC3，mC4和mC5的點(diǎn)可區(qū)別全染色數(shù)的相關(guān)結(jié)果，本文討論了m個(gè)長為6的圈的不交并mC6的點(diǎn)可區(qū)別全染色，并且確定了mC6的點(diǎn)可區(qū)別全色數(shù)。文中結(jié)論表明 VDTC 猜想對(duì)于圖mC6是成立的。文[9-10]對(duì)圖的奇優(yōu)美性及完美匹配計(jì)數(shù)給出了相關(guān)結(jié)論。

1　準(zhǔn)備工作

首先, 對(duì)任意的n≥ 9，構(gòu)造 (n-2)×(n-2)方陣An，并且使矩陣An的元素是空集或集合{1,2,…,n}的含n的3-子集：

設(shè)1≤i1

顯然, 矩陣An的6×1子矩陣B必是一個(gè)好組, 反之未必。如圖1所示,C6的6個(gè)頂點(diǎn)的色集合分別是 {c1,c2,c3}, {c3,c4,c5}, {c5,c6,c7}, {c7,c8,c9}, {c9,c10,c11} 和 {c11,c12,c1}。記這種染色為f(c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12)。

圖1　C6 的VDTC f (c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12)Fig.1　VDTCf(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12) of C6

引理1當(dāng)i≡1(mod 6)，j=1,2, …,n-2, 并且An[i,i+1,i+2,i+3,i+4,i+5 |j]中的元素都不是空集時(shí), 則An[i,i+1,i+2,i+3,i+4,i+5 |j]是一個(gè)好的6×1的子矩陣。

證明當(dāng)i≥1時(shí)，顯然,An[i,i+1,i+2,i+3,i+4,i+5 |j]的唯一一列的六個(gè)非空子集{n,j,j+i}, {n,j,j+i+1},…, {n,j,j+i+5}恰是在點(diǎn)可區(qū)別全染色f(n,j+i,j,j+i+1,n,j+i+2,j,j+i+3,n,j+i+4,j,j+i+5)下，C6 的全體頂點(diǎn)的色集合。

如果矩陣An的元素既不是引理1中任意好的6×1子矩陣的元素也不是空集, 那么稱矩陣An的元素是矩陣An的剩余元素。

由于引理2-引理5的證明過程類似, 下面僅給出引理5的詳細(xì)證明。

證明由引理1, 只需考慮矩陣An的剩余元素。

情形1當(dāng)n≡6(mod 12)。對(duì)i≡1 (mod 12), 6≤i≤n-12?？紤]矩陣An在第i,i+1,i+2,i+3,i+4,i+6,i+7,i+8,i+9和i+10列的剩余元素恰能劃分成5個(gè)好組，相應(yīng)的C6的VDTC分別是f(n,n-5,i,n-4,n,n-3,i,n-2,n,i,n-1,i+4),f(n,n-4,i+1,n-3,n,n-2,i+1,n-1,n,n-2,i+3,n-1),f(n,n-5,i+6,n-4,n,n-3,i+6,n-2,n,i+6,n-1,i+10),f(n,n-4,i+7,n-3,n,n-2,i+7,n-1,n,n-2,i+9,n-1)和f(n,n-3,i+2,n-2,n,i+2,n-1,i+8,n,n-3,i+8,n-2)。

矩陣An在第1,2,3和4列的剩余元素恰能劃分成1個(gè)好組, 相應(yīng)的C6的VDTC是f(n,n-4,1,n,n-3,2,n,n-2,3,n,n-1,4)。

顯然,An的剩余元素 {n,1,n-2},{n,1,n-1}, {n,2,n-2} 和 {n,2,n-1}不屬于任何一個(gè)好組。

情形2n≡ 9(mod 12)。對(duì)i≡1(mod 12), 9≤i≤n-12?？紤]矩陣An在第i,i+1,i+2,i+3,i+4,i+6,i+7,i+8,i+9和i+10列的剩余元素恰能劃分成5個(gè)好組, 相應(yīng)的C6的VDTC分別是f(n,n-5,i,n-4,n,n-3,i,n-2,n,i,n-1,i+4),f(n,n-4,i+1,n-3,n,n-2,i+1,n-1,n,n-2,i+3,n-1),f(n,n-5,i+6,n-4,n,n-3,i+6,n-2,n,i+6,n-1,i+10),f(n,n-4,i+7,n-3,n,n-2,i+7,n-1,n,n-2,i+9,n-1)和f(n,n-3,i+2,n-2,n,i+2,n-1,i+8,n,n-3,i+8,n-2)。

矩陣An在第3,4,5,6和7列的剩余元素恰能劃分成2個(gè)好組, 相應(yīng)的C6 的 VDTC分別是f(n,n-5,3,n-4,n,3,n-3,4,n,n-4,4,n-2) 和f(n,n-3,5,n-2,n,5,n-1,7,n,n-1,6,n-2)。

顯然,An的剩余元素{n,1,n-1},{n,3,n-2},{n,3,n-1}和{n,4,n-1}不屬于任何一個(gè)好組。

2　主要結(jié)果

證明顯然有χvt(mC6)≥μ(mC6)=k。因此只需給出mC6的k-VDTC 染色即可。

當(dāng)2≤m≤3,χvt(mC6)≥6,下面給出mC6的6-VDTC染色。3個(gè)C6能被f(1,2,3,4,2,1,4,1, 3,4,6,5),f(5,2,1,3,5,1,4,3,5,4,2,3)和f(6,2,1,3,6,1,4,2,6,5,2,3)分別染色, 所以χvt(3C6)=6。此時(shí)遺留下的3-子集為{6,3,5}和{6,4,5}, 而由3C6的染色很容易得到 2C6的 6-VDTC。

當(dāng)4≤m≤5,χvt(mC6)≥7, 在3C6的基礎(chǔ)上只需給出第4,5個(gè)C6的染色，分別如下:f(7,2,1, 3,7,4,1,5,7,1,6,5)和f(7,3,2,4,7,5,2,6,7,4,3,5)。所以χvt(5C6)=7。此時(shí)遺留下的3-子集為{6,3,5}, {6,4,5},{7,3,6},{7,4,5}和{7,4,6}, 而由5C6的染色很容易得到4C6的 7-VDTC。

當(dāng)6≤m≤9,χvt(mC6)≥8,在5C6的基礎(chǔ)上只需給出第6,7,8,9個(gè)C6的染色即可。mC6(m=6,7,8)的8-VDTC染色分別是f(8,2,1,3,8,4,1,5,8,6,1,7),f(8,3,2,4,8,5,2,6,8,2,7,6)和f(8,4,3,5,8,6,3,7,8,6,5,7)。由于{{6,3,5},{6,4,5},{7,3,6},{7,4,6},{8,4,6},{8,4, 7}}是一個(gè)好組, 因此可給第9個(gè)C6用f(6,3,5,4,6,3,7,6,4,7,8,4)進(jìn)行染色。

此時(shí)遺留下的3-子集為{7,4,5}和{8,4,5},而由9C6的染色很容易得到mC6(m=6,7,8)的 8-VDTC。

當(dāng) 10≤m≤14,χvt(mC6)≥9。在9C6的基礎(chǔ)上只需給出第10,11,12,13,14個(gè)C6的染色即可。mC6(m=10,11,12,13)的9-VDTC染色分別是f(9,2,1,3,9,4,1,5,9,6,1,7),f(9,3,2,4,9,5,2, 6, 9, 7, 2,8),f(9,4,3,5,9,6,3,7,9,3,8,1) 和f(9,5,4,6,9,7,4,8,9,7,8,6)。由于{{7,4,5}, {8,4,5}, {9,5,6}, {9,5,7}, {9,5,8},{9,6,7}}是一個(gè)好組, 因此可給第14個(gè)C6用f(7,5,4,8,5,6,9,7,5,8,9,6)進(jìn)行染色。至此,已把{1,2,…,9}中的所有 3-子集都用完。由14C6的9-VDTC易得到mC6(10≤m≤13)的9-VDTC。

注意:如果{1, 2,…,k} 的一個(gè)3-子集是mC6在k-VDTCg下的一個(gè)頂點(diǎn)的色集合, 那么這個(gè)3-子集稱為在g下用完。

定理1說明VDTC 猜想對(duì)mC6是成立的。

參考文獻(xiàn)：

[1]BURRIS A C, SCHELP R H.Vertex-distinguishing proper edge-colorings [J]. J of Graph Theory, 1997, 26(2): 73-82.

[2]BALISTER P N, RIORDAN O M, SCHELP R H. Vertex-distinguishing edge colorings of graphs [J]. J Graph Theory, 2003, 42: 95-109.

[3]BAZGAN C, HARKAT-BENHAMDINE A, LI H, et al. On the vertex-distinguishing proper edge-colorings of graphs [J]. J of Comb Theory(Series B), 1999, 75: 288-301.

[4]ZHANG Z F, QIU P X, XU B G, et al. Vertex-distinguishing total colorings of graphs [J]. Ars Combinatoria, 2008, 87: 33-45.

[5]陳祥恩，王治文，馬彥榮，等.mK4的點(diǎn)可區(qū)別全染色[J]. 吉林大學(xué)學(xué)報(bào)(理學(xué)版), 2012, 50(4): 686-692.

CHEN X E, WANG Z, MA Y R, et al. Vertex-distinguishing total colorings ofmK4[J]. Journal of Jilin University (Science Edition), 2012, 50(4): 686-692.

[6]辛小青，王治文，陳祥恩，等. 點(diǎn)不交的m個(gè)C3的并的點(diǎn)可區(qū)別全染色[J]. 吉林大學(xué)學(xué)報(bào)(理學(xué)版), 2012, 50(2): 251-257.

XIN X Q, WANG Z W, CHEN X E, et al. Vertex distinguishing total chromatic number ofmC3[J]. Journal of Jilin University (Science Edition), 2012, 50(2): 251-257.

[7]辛小青，陳祥恩.m個(gè)點(diǎn)不交的C4的并的點(diǎn)可區(qū)別全染色[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版), 2010, 45(10): 35-39.

XIN X Q, CHEN X E. Vertex distinguishing total chromatic number ofmC4[J]. Journal of Shandong University (Natural Science), 2010, 45(10): 35-39.

[8]CHEN X E, MA Y R, YANG F, et al. Vertex-distinguishing total colorings ofmC5[J], Applied Mechanics and Materials, 2013, 321/324: 578-581.

[9]孫慧，姚兵. 探索圈龍圖的奇優(yōu)美性[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2017, 56(4): 9-15.

SUN H, YAO B. Exploring the odd gracefulness of cyclic-dragon graphs [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2017, 56(4): 9-15.

[10]唐保祥，任韓. 2類圖完美匹配數(shù)目的解析式[J].中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 55(4): 15-17.

TANG B X, REN H. The analytic formula of the number of perfect matchings of two types of graphs [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(4): 15-17.