馬寶林,張振亮,姚瑞

（河南科技學(xué)院,河南新鄉(xiāng)453003）

若干個(gè)C3并的點(diǎn)可區(qū)別V-全染色

馬寶林,張振亮,姚瑞

（河南科技學(xué)院,河南新鄉(xiāng)453003）

根據(jù)簡單圖的點(diǎn)可區(qū)別V-全染色的概念及其染色方法,討論若干個(gè)階為3的圈的頂點(diǎn)不交并的點(diǎn)可區(qū)別V-全染色,并給出其全色數(shù)及染色方案,為進(jìn)一步探討mCn的點(diǎn)可區(qū)別V-全染色提供了理論證據(jù),豐富了圖的點(diǎn)可區(qū)別V-全染色的結(jié)果.

簡單圖；全色數(shù)；點(diǎn)可區(qū)別V-全染色；圈的頂點(diǎn)不交并

張忠輔、陳祥恩等于2004年在圖的全染色概念的基礎(chǔ)上提出了鄰點(diǎn)可區(qū)別全染色概念[1],2008年,他們又在點(diǎn)可區(qū)別正常全染色的基礎(chǔ)上提出了圖的點(diǎn)可區(qū)別一般全染色[2].本文將從簡單圖的點(diǎn)可區(qū)別V-全染色的定義出發(fā),討論mC3的點(diǎn)可區(qū)別V-全染色并給出其全色數(shù)及證明．

1 相關(guān)概念

文獻(xiàn)[1]和[2]中給出了簡單圖的點(diǎn)可區(qū)別正常全染色的研究,并用表示圖的點(diǎn)可區(qū)別全色數(shù).

定義1設(shè)G為一個(gè)階不小于2的簡單連通圖,k是一個(gè)正整數(shù),A：{1,2,…,k}為一個(gè)色集合,如果以下3個(gè)條件被滿足：（v）對(duì)uv∈E（G）,有f( u)≠f( v)；（e）對(duì)uv,vw∈E（G）,u≠w,有f( uv)≠f( vw)；（i）對(duì)uv∈E（G）,有f( u)≠f( v)≠f( uv ).則f稱為G的正常全染色．

上述條件中,若只滿足其中一個(gè)或兩個(gè)條件時(shí)就被稱之為圖的一般全染色.本文僅考慮只滿足（e）和（i）時(shí)的情形.

定義2設(shè)G是一個(gè)簡單圖,k是正整數(shù),f是一個(gè)從V（G）∪E（G）到集合{1,2,…,k}的映射,對(duì)圖G的一個(gè)全染,用C（u）表示點(diǎn)u和它所關(guān)聯(lián)的邊所染的顏色組成的集合.若對(duì)于G的任意兩點(diǎn)u和v,都有C（u）≠C（v）,則稱是圖G的點(diǎn)可區(qū)別V-全染色,簡稱為圖G的VDVT染色.

圖G的一個(gè)VDVT染色所需要的最少顏色的數(shù)目稱為圖G的點(diǎn)可區(qū)別V-全色數(shù),記為(G).

2 圖mC3的點(diǎn)可區(qū)別V-全染色

由點(diǎn)可區(qū)別V-全染色的定義可知,所有頂點(diǎn)的色集合均為3-組合.當(dāng)n≥3時(shí),可以將所有與n關(guān)聯(lián)的3-組合用矩陣Mn給出：

（未寫出的元素均為空集φ）．

定義3在矩陣Mn中,任取3個(gè)元素（不能是空集）,并按其原來順序構(gòu)成的矩陣,稱為矩陣Mn的一個(gè)子塊；若Mn的一個(gè)子塊恰好可以完成一個(gè)C3的點(diǎn)可區(qū)別V-全染色,則稱這個(gè)子塊為一個(gè)好子塊,記為I.

若將矩陣Mn中所有好子塊去掉后,剩余元素構(gòu)成的集合成為余集,記為An．

下面給出幾種常用的好子塊,如下圖所示,并給出它們的一般表達(dá)式及其對(duì)C3的點(diǎn)可區(qū)別V-全染色方案：

I1,易知色集合{s,t,k},{k,s+1,t+1},{t+1,k,s}可以完成一個(gè)C3的VDVT染色；

I2,易知色集合{t,s,k},{k,t+1,s+1},{s+1,k,t}可以完成一個(gè)C3的VDVT染色；

I3,易知色集合{s,k,t},{t,s+1,k},{k,t+1,s}可以完成一個(gè)C3的VDVT染色；

I4,易知色集合{k,s,t+1},{t+1,k,s+1},{s+1,t,k}可以完成一個(gè)C3的VDVT染色；

I5,易知色集合{s+1,s,k},{k,s+3,s+2},{s+2,k,s+1}可以完成一個(gè)C3的VDVT染色．

引理2對(duì)任意正整數(shù)n（n≥3）構(gòu)成的矩陣Mn,均可拆分為若干個(gè)好子塊的并,并且其余集所含元素的個(gè)數(shù)不大于1．

特別地,當(dāng)n=3m（m≥1）時(shí),剩余一個(gè)元素；當(dāng)n=3m+1（m≥1）時(shí),無剩余元素；當(dāng)n=3m+2（m≥1）時(shí),也無剩余元素,并且當(dāng)所余元素累積到3個(gè)時(shí),恰好可以構(gòu)成一個(gè)好子塊．

證明：當(dāng)n=3時(shí),M3=（1,2,3）,={{1,2,3}}；

當(dāng)n=5時(shí),M5

即M7=

當(dāng)n=8時(shí),M8

當(dāng)n=9時(shí),M9=

易知A3∪A6∪A9={{2,3,1},{1,9,4},{4,6,2}},恰好可以完成一個(gè)C3的VDVT染色．

綜上,當(dāng)n≥10時(shí),在上述拆分的基礎(chǔ)上遞推,并分3種情況討論.假定前n＜3k時(shí),引理2成立,則：

（1）當(dāng)n=3k時(shí),先根據(jù)M3k-2的結(jié)構(gòu)拆分矩陣M3k的后3k-4行元素,再考慮拆分前兩行元素.因?yàn)镸3k共有3k-2列,則前兩行元素中可以拆分為

當(dāng)k=3（3m-2）（,m≥1）時(shí),將F拆分為{1,2,3k}∪I2∪I1,

當(dāng)k=3（3m-1）（,m≥1）時(shí),將F拆分為I1∪{1,4,3k}∪I4,

當(dāng)k=3（3m）（,m≥1）時(shí),將F拆分為I1∪{1,4,3k}∪I4,

易知A3(3m-2)∪A3(3m-1)∪A3(3m)={{2,3(3m-2),1},{1,3(3m),4},{4,3(3m -1),2}},恰好可以完成一個(gè)的VDVT染色.

（2）當(dāng)n=3k+1時(shí),先根據(jù)M3k-1的結(jié)構(gòu)拆分矩陣M3k+1的后3k-3行元素,再考慮拆分前兩行元素.因?yàn)镸3k+1共有3k-1列,則前兩行元素可以拆分為I1∪(k-1)(I2∪I1)．

因此,M3k+1可以拆分為個(gè)好子塊,并且沒有剩余元.

（3）當(dāng)n=3k+2時(shí),先根據(jù)M3k的結(jié)構(gòu)拆分矩陣M3k+2的后3k-2行元素（會(huì)剩余一個(gè)元素）,再考慮拆分前兩行元素.因?yàn)镸3k+2共有3k列,此時(shí),可分為3種情況：

當(dāng)k=3（3m-2）,（m≥1）時(shí),前兩行與剩下那個(gè)元素{3,4,3k}可拆分為,顯然{1,2,3k+2},{2,3,3k+2},{3,4,3k}可以完成一個(gè)C3的VDVT染色；

當(dāng)k=3（3m-1）,（m≥1）時(shí),前兩行與剩下那個(gè)元素{4,6,3k+2}可拆分為I1∪{2,5,3k+2}∪I2∪{2,6,3k+2}∪（k-2）（I2∪I1）∪{4,6,3k+2},顯然,{2,5,3k+2},{3k+2,4,6},{6,3k+2,2}可以完成一個(gè)C3的VDVT染色；

當(dāng)k=3（3m）,（m≥1）時(shí),前兩行與剩下那個(gè)元素{3,6,3k+2}可拆分為∪（k-3）（I2∪I1）∪{4,6,3k+2}顯然,{2,5,3k+2},{3k+2,3,6},{6,3k+2,2}可以完成一個(gè)C3的VDVT染色；

因此,M3k+2可以拆分為個(gè)好子塊,并且沒有剩余元.

綜上,引理成立.

由引理2,若每個(gè)好子塊均為一個(gè)C3的點(diǎn)可區(qū)別V-全染色,則可得到mC3的點(diǎn)可區(qū)別V-全染色,容易推出下面定理.

3 小結(jié)

本文根據(jù)圖的點(diǎn)可區(qū)別V-全染色的概念,給出m個(gè)階為3的圈的并的點(diǎn)可區(qū)別V-全染色,并利用歸納法給出了完整的證明,為進(jìn)一步探討更高階的圈的并的染色問題提供了思想方法,豐富了圖的點(diǎn)可區(qū)別全染色的結(jié)論,為解決排課表問題、通訊網(wǎng)等實(shí)際問題給出了有力的理論依據(jù).

[1]Zhang Z F,Chen X E.On adjacent-vertex-distinguishing total coloring of graphs[J].Science in China（Ser A）,2005,48（3）：289-299.

[2]陳祥恩.n-方體的點(diǎn)可區(qū)別全色數(shù)的漸進(jìn)性態(tài)[J].西北師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2005,41（5）：1-3.

[3]張忠輔,陳祥恩,李敬文,等.關(guān)于圖的鄰點(diǎn)可區(qū)別全染色[J].中國科學(xué)A輯：數(shù)學(xué),2004,34（5）：574-583.

[4]馬寶林,劉娟,陳祥恩.圖mP2與mP3的點(diǎn)可區(qū)別E-全染色[J].讀寫算,2010（9）：201-202.

[5]Ma B L,Chen X E,Liu J.2-distance coloring of strong product of graphs[J].山東大學(xué)學(xué)報(bào),2010,45（3）：66-70.

[6]Zheng Z F,Qiu P X,Xu B G,et al.Vertex-distinguishing total colorings of graphs[J].Ars Combinatoria,2008（87）：33-45.

[7]馬寶林.完全圖的點(diǎn)可區(qū)別V-全染色[J].河南科技學(xué)院學(xué)報(bào)：自然科學(xué)版,2011,39（5）：44-46.

[8]馬寶林.關(guān)于路的并的點(diǎn)可區(qū)別V-全染色[J].河南科技學(xué)院學(xué)報(bào)：自然科學(xué)版,2012,40（3）：65-68.

（責(zé)任編輯：盧奇）

Vertex distinguishing V-total chromatic on number of mC3

Ma Baolin,Zhang Zhenliang,Yao Rui
（Henan Institute of Science and Technology,Xinxiang 453003,China）

According to definition and method of vertex-distinguishing,V-total coloring,the vertex-distinguishing V-total coloring of the vertex-disjoint union of mC3were discussed mainly and gave vertex-distinguishing V-total chromatic number,which provided a theoretical evidence for prospective studies of mCn vertex-distinguishing V-total coloring and enriched results of graph vertex-distinguishing V-total coloring.

simple graph；chromatic number；Vertex-distinguishing V-total coloring；the vertex-disjoint union of circles.

O157.5

A

1008-7516（2013）06-0025-04

10.3969/j.issn.1008-7516.2013.06.007

2013-09-04

河南省教育科學(xué)“十二五”規(guī)劃項(xiàng)目（2013-JKGHD-0349）

馬寶林（1978-）,男,回族,甘肅張家川人,碩士,副教授.主要從事圖論、數(shù)學(xué)文化研究.