張 琛，李紅霞

(隴東學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅慶陽745000)

k-樹及其鄰點可區(qū)別全染色

張 琛，李紅霞

(隴東學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅慶陽745000)

G是一個簡單圖，G的一個全染色f是指使相鄰頂點和相鄰邊著不同顏色且每條關(guān)聯(lián)邊與它的頂點著以不同顏色的全染色。設(shè)f為圖G一個全染色，對任意x∈V(G)，用C(x)表示在f下頂點的顏色以及與x關(guān)聯(lián)的邊的顏色所構(gòu)成的集合。若任意uv∈E(G)，u≠v，有C(u)≠C(v)，則稱f是圖G的鄰點可區(qū)別的全染色，該問題的主要目的是確定圖G的鄰點可區(qū)別全色數(shù)?；跇涞幕窘Y(jié)構(gòu)，構(gòu)造了一種新的圖類—k-樹，討論并給出了兩類k-樹S(n,1)，S(n,2)的鄰點可區(qū)別全色數(shù)。

樹；k-樹；鄰點可區(qū)別全染色；鄰點可區(qū)別全色數(shù)

凡有二元關(guān)系的系統(tǒng)，圖論均可提供一種數(shù)學(xué)模型——圖。要討論客觀世界中某些具體事物間的聯(lián)系，則用頂點代表事物，用邊表示各事物間的二元關(guān)系；如果所討論的事物之間有某種二元關(guān)系，我們就把相應(yīng)的頂點連成一條邊。這種由頂點及連接這些頂點的邊所組成的圖就是所研究的對象。在圖論眾多的圖類中，樹是非常重要的一類圖，它是最簡單的連通圖，許多問題對一般連通圖未能解決或者沒有簡單的方法，而對于樹，則已圓滿解決，且方法較為簡單。受文獻[1]啟發(fā)，本文基于樹的基本結(jié)構(gòu)，構(gòu)造了一種新的圖類——k-樹。

圖論研究中的一個重要方向是圖的染色問題。許多實際問題都可以轉(zhuǎn)化為圖的染色模型，例如資源配置、印刷電路布線、加載問題、頻率分配等。1985年，HararyF等人開始研究圖的點可區(qū)別的一般邊染色；ChartrandG，JacobsonM，LehelJ等人于1986年研究圖的可允許的一般邊染色(即頂點被關(guān)聯(lián)邊的顏色之和可區(qū)別的一般邊染色，所使用的顏色是從1開始的相繼的正整數(shù))所需要的顏色的最少數(shù)目即圖的非正規(guī)強度；BurrisAC，SchelpRH則于1993年提出圖的點可區(qū)別正常邊染色。自2002年以來，張忠輔教授相繼提出圖的鄰點可區(qū)別正常邊染色，鄰點可區(qū)別正常全染色，點可區(qū)別正常全染色等新的圖染色概念之后，圖的可區(qū)別染色受到越來越多學(xué)者的重視。特別是2004年，在全染色的基礎(chǔ)上，張忠輔，陳祥恩等人提出了鄰點可區(qū)別的全染色這一概念(見參考文獻[2]，此文榮獲2008年度“中國百篇最具影響國內(nèi)文章”。該文的英文版見參考文獻[3])，使得圖論界產(chǎn)生了許多更有趣的問題(如子圖的鄰點可區(qū)別全色數(shù)不一定比母圖小)，并且已得到了一些有價值的成果[4-10]。因此，本文也將對k-樹圖的鄰點可區(qū)別全染色進行討論。

1 定義及引理

本文所考慮的圖均為有限、無向的簡單圖。Δ(G)，d(v)分別表示圖G的最大度和圖G中頂點v的度。其它術(shù)語及符號參照文獻[2]。

定義1.1[11]一個n階圖Tn是樹當(dāng)且僅當(dāng)Tn中任意兩個不同頂點之間有且只有一條路連接。

定義1.2[2]含有n-1個懸掛點的n階樹Tn，稱為n階星Sn。

定義1.3[11]對圖G(V(G),E(G))，k是正整數(shù)，S是k元集，f是從V(G)∪E(G)到S的映射。如果

1)?uv,vw∈E(G)，u≠w，有f(uv)≠f(vw)， 2)?uv∈E(G)，有f(u)≠f(v)，f(u)≠f(uv)，f(uv)≠f(v)，

定義1.4[2]對圖G(V(G),E(G))，t是正整數(shù)，S是t元集，f是從V(G)∪E(G)到S的映射。如果

1)f是圖G的正常全染色，

由定義可知：一個圖G的鄰點可區(qū)別全染色，一定是圖G的正常全染色，因此顯然有，χt(G)≤χat(G)。又由于一個圖的鄰點可區(qū)別全色數(shù)等于它的各個分支的鄰點可區(qū)別全色數(shù)的最大值，因此以下均考慮連通圖。

引理1.1[2]對任一圖G，有

ⅰ)χat(G)≥Δ(G)+1；

ⅱ)當(dāng)圖G具有兩個相鄰的最大度點時，χat(G)≥Δ(G)+2。

引理1.2[2]若Tn為n階樹(n≥4)，則：

引理1.3[2]若Sn為n階星(n≥4)，則χat(Sn)=n。

在文獻[2,3]中，張忠輔等人提出了關(guān)于鄰點可區(qū)別全色數(shù)的猜想：對n階圖G，有χat(G)≤Δ(G)+3。

本文將證明該猜想對于兩類k-樹的鄰點可區(qū)別全色數(shù)是成立的。首先我們給出k-樹圖的定義。

定義1.5 對n階樹Tn，k為正整數(shù)，若圖G的頂點集合與邊集合分別為：

V(G)=V(Tn)∪{v1,v2,…,vk}={u1,u2,…un,v1,v2,…,vk}，

E(G)=E(Tn)∪{uiv1,uiv2,…,uivn,i=1,2,…,n}，

若n階樹Tn為n階星Sn，則當(dāng)k=1時，該類k-樹記為S(n,1)；當(dāng)k=2時，該類k-樹記為S(n,2)。圖1為n=4，n=5時兩類k-樹的結(jié)構(gòu)模式。

圖1 兩類k-樹的結(jié)構(gòu)模式

文中確定了S(n,1)與S(n,2)的鄰點可區(qū)別全色數(shù)。①當(dāng)n=1時，S(n,1)與S(n,2)均為一條路，文獻[2]中得到χat(P2)=χat(S(1,1))=3，χat(P3)=χat(S(1,2))=3。②當(dāng)n=2時，S(n,1)為圈C3，同樣在文獻[2]中已得到χat(C3)=4；S(n,2)為完全圖K4的一個子圖，易得χat(S(2,2))=4，圖2(a)給出了S(2,2)的一種鄰點可區(qū)別全染色。③當(dāng)n=3時，S(3,1)與S(2,2)同構(gòu)；S(3,2)是最大度為4的廣義Halin圖，易得χat(S(3,2))=5，圖2(b)給出了S(3,2)的一種鄰點可區(qū)別全染色，同時該結(jié)論也支持文獻[12]中關(guān)于廣義Halin圖的鄰點可區(qū)別全染色猜想。

圖2 兩類k-樹的染色方案

故以下不妨設(shè)n≥4。

2 主要結(jié)果

定理2.1 對k-樹S(n,1)，n≥4，有χat(S(n,1))=n+2。

證明 若記

V(S(n,1))={u,u1,u2,…,un-1,v}，

E(S(n,1))={uui,uiv,uv,i=1,2,…,n-1}，則u與v為S(n,1)中唯一一對相鄰的最大度點，且d(u)=d(v)=n。

因為Δ(S(n,1))=n且S(n,1)中有兩個相鄰的最大度點，由引理2.1可知：

χat(S(n,1))≥Δ(S(n,1))+2=n+2，

以下討論S(n,1)可用n+2種色進行其鄰點可區(qū)別全染色。

f(ui)=i，i=1,2,…,n-1，f(u)=n+1，

f(uui)=i+1，i=1,2,…n-1。

其次對頂點v及與頂點v關(guān)聯(lián)的邊正常染色，

f(v)=n+2，f(uv)=1，

f(uiv)=i+2，i=1,2,…,n-2，f(un-1v)=2。

在上述染色方案中，

C(u)={1,2,…,n,n+1}，C(v)={1,2,…,n,n+2}，

C(ui)={i,i+1,i+2}，i=1,2,…,n-2，C(un-1)={2,n-1,n}。

下面說明染色方案f是S(n,1)的鄰點可區(qū)別全染色。

定理2.2 對k-樹S(n,2)，n≥4，有χat(S(n,2))=n+2。

證明 若記

V(S(n,2))={u,u1,u2,…,un-1,v1,v2}，

E(S(n,2))={uui}∪{uiv1,uv1}∪{uiv2,uv2}，其中i=1,2,…,n-1，

則u為S(n,1)中唯一的最大度點，且d(u)=n+1。

因為Δ(S(n,2))=n+1且S(n,2)中沒有相鄰的最大度點，由引理1.1可知：

χat(S(n,2))≥Δ(S(n,2))+1=n+2，

以下討論S(n,2)可用n+2種顏色進行其鄰點可區(qū)別全染色。

令S={1,2,…,n+2}，用S中的顏色構(gòu)造S(n,2)的染法f，如下：

f(ui)=i，i=1,2,…,n-1，f(u)=n+1，

f(uui)=i+1，i=1,2,…,n-1。

其次對頂點v1及與頂點v1關(guān)聯(lián)的邊正常染色，

f(v1)=n+2，f(uv1)=1，

f(uiv1)=i+2，i=1,2,…,n-1。

再次對頂點v2及與頂點v2關(guān)聯(lián)的邊正常染色，

f(v2)=n，f(uv2)=n+2，

f(u1v2)=n+1，f(uiv2)=i-1，i=2,3,…,n-1。

在上述染色方案中，

C(u)={1,2,…,n+2}，

C(v1)={1}∪{3,4,…,n+2}，C(v2)={1,2}∪{4,5,…,n+2}，

C(u1)={1,2,3,n+1}，C(ui)={i-1,i,i+1,i+2}，i=2,3,…,n-1。

下說明染色方案f是S(n,2)的鄰點可區(qū)別全染色。

根據(jù)定理2.1和2.2的證明，我們有一個猜想：k-樹S(n,k)，k為正整數(shù)，n≥4，有χat(S(n,k))=n+2。對該猜想的證明可沿用定理2.1和2.2的證明方式，但敘述是困難的，所以在以后的研究中我們將考慮借助于機器證明。

[1]馬德山,劉林忠,張忠輔.1-樹圖的鄰強邊染色[J].數(shù)學(xué)研究與評論,2000(2):299-305.

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

[3]ZHANGZhong-fu,CHENXiang-en,LiJingwen,等.Onadjacent-vertex-distinguishingtotalcoloringofgraphs[J].中國科學(xué)A輯(英文版)，2005(3):289-299.

[4]CHENXiang-en,ZHANGZhong-fu.Adjacent-vertex-DistinguishingtotalchromaticnumberonMycielski'sgraphsofseveralkindsofparticulargraphs[J].JournalofLanzhouUniversity(NaturalScience),2005,41(2):117-122.

[5]CHENXiang-en,ZHANGZhong-fu.Adjacent-Vertex-distinguishingTotalchromaticnumberofPm×Kn[J].數(shù)學(xué)研究與評論，2006,26(3):489-494.

[6]CHENXiang-en,ZHANGZhong-fu.Adjacent-vertex-distinguishingtotalchromaticnumberon2-connectedouterplanegraphwithΔ(G)≤4[J].蘭州大學(xué)學(xué)報(自然科學(xué)版)，2006,49(6):703-708.

[7]陳祥恩,張琛.直積圖的鄰點可區(qū)別全染色[J].蘭州理工大學(xué)學(xué)報，2008(2):137-140.

[8]張琛,陳祥恩,劉信生.多重Mycielski圖的鄰點可區(qū)別全染色[J].西北師范大學(xué)學(xué)報(自然科學(xué)版)，2007(6):22-26.

[9]張琛,張如清,呂衛(wèi)東.K2s×K2t的鄰點可區(qū)別全染色[J].數(shù)學(xué)的實踐與認(rèn)識,2012(20):213-216.

[10]張琛,王欣欣.K2n-1×K2n+1的鄰點可區(qū)別全染色[J].佳木斯大學(xué)學(xué)報(自然科學(xué)版),2013,31(3):464-466.

[11]BONDYJA,MURTYUSR.Graphtheorywithapplications[M].NewYork:Macmillan,1976:91-134.

[12]陳祥恩.圖的可區(qū)別染色引論[M].北京:中國科學(xué)技術(shù)出版社,2015:146-246.

【責(zé)任編輯 朱世廣】

The Adjacent Vertex-distinguishing Total coloring ofk- tree

ZHANG Chen，LI Hong-Xia

(SchoolofMathematicsandStatistics,LongdongUniversity,Qingyang745000,Gansu)

LetGbe a simple graph. A total coloring f ofGis called an total coloring if no two adjacent vertices and no two adjacent edges ofGreceive the same color, and no edge of receives the same color as one of its endpoints. For an total coloringfof a graph and any vertex ofG, letC(x) denote the set of colors of vertex x and of the edges incident withx, we callC(x) the color set ofx. IfC(u)≠C(v) for any two adjacent vertexesuandvofV(G), then we say thatfis a adjacent vertex-distinguishing total coloring ofG. The main purpose of this problem is to determine the adjacent vertex-distinguishing total chromatic number ofG. In this paper, a new graph,k- tree, is constructed on the base of the structure of the tree. The adjacent vertex-distinguishing total chromatic number onk- tree are obtained for some special graphs, such asS(n,1) andS(n,2).

tree;k- tree; adjacent vertex-distinguishing total coloring; adjacent vertex-distinguishing total chromatic number

1674-1730(2017)01-0011-04

2016-06-13

甘肅省高等學(xué)校科研項目《模糊圖在網(wǎng)絡(luò)優(yōu)化中的應(yīng)用研究》(2015A-144)

張 琛(1983—)，女，甘肅慶陽人，講師，碩士,主要從事圖的染色理論研究。

O

A