若干個C3并的點可區(qū)別V-全染色

馬寶林,張振亮,姚瑞

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

若干個C3并的點可區(qū)別V-全染色

馬寶林,張振亮,姚瑞

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

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

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

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

1 相關概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

特別地,當n=3m（m≥1）時,剩余一個元素；當n=3m+1（m≥1）時,無剩余元素；當n=3m+2（m≥1）時,也無剩余元素,并且當所余元素累積到3個時,恰好可以構成一個好子塊．

證明：當n=3時,M3=（1,2,3）,={{1,2,3}}；

當n=5時,M5

即M7=

當n=8時,M8

當n=9時,M9=

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

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

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

當k=3（3m-2）（,m≥1）時,將F拆分為{1,2,3k}∪I2∪I1,

當k=3（3m-1）（,m≥1）時,將F拆分為I1∪{1,4,3k}∪I4,

當k=3（3m）（,m≥1）時,將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}},恰好可以完成一個的VDVT染色.

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

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

（3）當n=3k+2時,先根據(jù)M3k的結(jié)構拆分矩陣M3k+2的后3k-2行元素（會剩余一個元素）,再考慮拆分前兩行元素.因為M3k+2共有3k列,此時,可分為3種情況：

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

當k=3（3m-1）,（m≥1）時,前兩行與剩下那個元素{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}可以完成一個C3的VDVT染色；

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

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

綜上,引理成立.

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

3 小結(jié)

本文根據(jù)圖的點可區(qū)別V-全染色的概念,給出m個階為3的圈的并的點可區(qū)別V-全染色,并利用歸納法給出了完整的證明,為進一步探討更高階的圈的并的染色問題提供了思想方法,豐富了圖的點可區(qū)別全染色的結(jié)論,為解決排課表問題、通訊網(wǎng)等實際問題給出了有力的理論依據(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-方體的點可區(qū)別全色數(shù)的漸進性態(tài)[J].西北師范大學學報：自然科學版,2005,41（5）：1-3.

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

[4]馬寶林,劉娟,陳祥恩.圖mP2與mP3的點可區(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].山東大學學報,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]馬寶林.完全圖的點可區(qū)別V-全染色[J].河南科技學院學報：自然科學版,2011,39（5）：44-46.

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

（責任編輯：盧奇）

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

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

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