一類(lèi)含有4-圈的單圈圖一般點(diǎn)可區(qū)別全染色

陳 祥 恩， 李 婷， 王 治 文

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

一類(lèi)含有4-圈的單圈圖一般點(diǎn)可區(qū)別全染色

陳 祥 恩*1， 李 婷1， 王 治 文2

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

設(shè)G為簡(jiǎn)單圖．設(shè)f是圖G的一個(gè)一般全染色，若對(duì)圖G的任意兩個(gè)不同的頂點(diǎn)u、v，有C(u)≠C(v)，則稱(chēng)f為圖G的一般點(diǎn)可區(qū)別全染色(簡(jiǎn)記為GVDTC)．對(duì)圖G進(jìn)行一般點(diǎn)可區(qū)別全染色所需要的最少顏色數(shù)稱(chēng)為圖G的一般點(diǎn)可區(qū)別全色數(shù)．將一類(lèi)含有4-圈的單圈圖懸掛邊的染色按從小到大的順序排列，探討了它的一般點(diǎn)可區(qū)別全染色，確定了它具有一般點(diǎn)可區(qū)別全染色，并得到了它的一般點(diǎn)可區(qū)別全色數(shù)．

單圈圖；一般全染色；一般點(diǎn)可區(qū)別全染色；一般點(diǎn)可區(qū)別全色數(shù)

0 引 言

點(diǎn)可區(qū)別一般邊染色是由Harary等于1985年在文獻(xiàn)[1]中提出的，文獻(xiàn)[2-4]對(duì)此也進(jìn)行了研究．近些年來(lái)點(diǎn)可區(qū)別的未必正常的全染色也逐漸被研究．例如，點(diǎn)可區(qū)別IE-全染色在文獻(xiàn)[5]中被提出，而一般點(diǎn)可區(qū)別全染色也在文獻(xiàn)[6]中被提出．本文受文獻(xiàn)[6]的啟發(fā)，使用更為簡(jiǎn)單的方法探討一類(lèi)含有4-圈的單圈圖的一般點(diǎn)可區(qū)別全染色，并得到它的一般點(diǎn)可區(qū)別全色數(shù)．

1 準(zhǔn)備工作

圖G的一個(gè)一般全染色是指若干種顏色對(duì)圖G的全體頂點(diǎn)及邊的一個(gè)分配．

設(shè)f為圖G的一個(gè)一般全染色或IE-全染色，x為圖G的一個(gè)頂點(diǎn)，將在f下x的顏色及與x關(guān)聯(lián)的邊的顏色所構(gòu)成的集合(非多重集)記為Cf(x)或C(x)，稱(chēng)之為頂點(diǎn)x在f下的色集合，即C(x)={f(xu)|xu∈E}∪{f(x)}．

設(shè)f為圖G的一般全染色，若對(duì)圖G的任意兩個(gè)不同的頂點(diǎn)u、v，有C(u)≠C(v)，則稱(chēng)f為圖G的點(diǎn)可區(qū)別一般全染色或者一般點(diǎn)可區(qū)別全染色(簡(jiǎn)記為GVDTC)．圖G的使用了k種顏色的一般點(diǎn)可區(qū)別全染色稱(chēng)為圖G的k-一般點(diǎn)可區(qū)別全染色(簡(jiǎn)記為k-GVDTC)．對(duì)圖G進(jìn)行一般點(diǎn)可區(qū)別全染色所需要的最少顏色數(shù)稱(chēng)為圖G的一般點(diǎn)可區(qū)別全色數(shù)，記為χgvt(G)．

星Sn就是完全二部圖K1,n(n≥1)．稱(chēng)Sm,n是雙星，如果Sm,n是樹(shù)，并且頂點(diǎn)集為V(Sm,n)={ui|i=0，1，…，m}∪{vj|j=0，1，…，n}，邊集為E(Sm,n)={u0ui|i=0，1，…，m}∪{v0vj|j=0，1，…，n}∪{u0v0}，其中m、n是正整數(shù)且均大于1．稱(chēng)Sp，q，r是三星，如果Sp，q，r是樹(shù)，并且頂點(diǎn)集為V(Sp，q，r)={ui|i=0，1，…，p}∪{vj|j=0，1，…，q}∪{wt|t=0，1，…，r}，邊集為E(Sp，q，r)={u0ui|i=0，1，…，p}∪{v0vj|j=0，1，…，q}∪{w0wt|t=0，1，…，r}∪{u0v0，v0w0}，其中p、q、r是正整數(shù)且均大于1．

本文設(shè)C4；m1，m2，m3，m4表示如圖1所示的一類(lèi)含有4-圈的單圈圖．

文獻(xiàn)[6]中研究了路、圈、星(即K1,n)、雙星、三星、輪、扇、完全圖的一般點(diǎn)可區(qū)別全染色，確定了它們的一般點(diǎn)可區(qū)別全色數(shù)．本文將探討一類(lèi)含有4-圈的單圈圖C4；m1，m2，m3，m4的一般點(diǎn)可區(qū)別全染色，并確定它們的一般點(diǎn)可區(qū)別全色數(shù)．

圖1 一類(lèi)含有4-圈的單圈圖

引理1[6]設(shè)Sn(n≥1)是一個(gè)星，則

χgvt(Sn)= 2；n=1，23；n=38n+1-12；n≥4ì?í??????

2 主要結(jié)果及其證明

定理1 設(shè)C4；m1，m2，m3，m4(mi≥1，i=1，2，3，4)是一個(gè)含有4-圈的單圈圖，令l=m1+m2+m3+m4，則

χgvt(C4；m1，m2，m3，m4)= 4；l=4，5，68l+1-12；l≥7ì?í????

證明 當(dāng)l=4時(shí)，顯然χgvt(C4；1，1，1，1)≥4．因?yàn)?種顏色只能區(qū)別7個(gè)點(diǎn)，而圖2(a)給出了C4；1，1，1，1的4-GVDTC，因此χgvt(C4；1，1，1，1)=4．

當(dāng)l=5時(shí)，顯然χgvt(C4；1，1，1，2)≥4．因?yàn)?種顏色只能區(qū)別7個(gè)點(diǎn)，而圖2(b)給出了C4；1，1，1，2的4-GVDTC，因此χgvt(C4；1，1，1，2)=4．

當(dāng)l=6時(shí)，只需考慮C4；1，1，1，3、C4；1，1，2，2、C4；1，2，1，2即可．顯然對(duì)這3個(gè)圖，χgvt≥4，而圖2(c)、(d)、(e)分別給出了3個(gè)圖的4-GVDTC，故χgvt(C4；1，1，1，3)=χgvt(C4；1，1，2，2)=χgvt(C4；1，2，1，2)=4．

以下假設(shè)l≥7．

k=8l+1-12

(a) C4;1,1,1,1

(b) C4;1,1,1,2

(c) C4;1,1,1,3

(d) C4;1,1,2,2

(e) C4;1,2,1,2

讓C4；m1，m2，m3，m4的懸掛點(diǎn)ui，j沿襲在g下G′中對(duì)應(yīng)的懸掛點(diǎn)ui，j的顏色，j=1，2，…，mi，i=1，2，3，4；讓C4；m1，m2，m3，m4的懸掛邊uiui，j沿襲在g下G′中對(duì)應(yīng)的懸掛邊wui，j的顏色，j=1，2，…，mi，i=1，2，3，4．則在此基礎(chǔ)上以下只需考慮u1、u1u2、u2、u2u3、u3、u3u4、u4、u1u4的染色即可．

令A(yù)ui表示與ui關(guān)聯(lián)的懸掛邊的顏色構(gòu)成的集合(非多重集)，i=1，2，3，4．以下分5種情況討論：

在這種情況下，可按圖3(a)、(b)、(c)、(d)、 (e) 所給出的方式分5種情形對(duì)圈上的點(diǎn)、邊進(jìn)行染色．比如：在情形(a)中，邊u1u2、u2u3、u3u4、u1u4分別用3、4、4、1染色；點(diǎn)u1、u2、u3、u4分別用2、2、3、2染色．這時(shí)，Cf(u1)={1，2，3}，Cf(u2)={1，2，3，4}，Cf(u3)={1，3，4}，Cf(u4)={1，2，4}，其他頂點(diǎn)即懸掛點(diǎn)的色集合為1-子集或2-子集．因此所得的染色是k-GVDTC．在其他情形下，都可類(lèi)似得到最終染色是k-GVDTC，且不再贅述．

(a)

(b)

(c)

(d)

(e)

圖3 情況(1)的示意圖

Fig.3 The schematic graph of case (1)

情形(a)記為情形(1，1，1，1)，情形(b)記為情形(1，1，1，2)，其他類(lèi)似．除上述5種情形外，還有情形(1，2，2，2)等價(jià)于情形(b)；情形(1，2，2，3)與(1，2，3，3)均等價(jià)于情形(d)．因此，出現(xiàn)的這些情形將不再畫(huà)圖表示．

注記 圖3均為示意圖，在圖中只標(biāo)出了與u1、u2、u3、u4關(guān)聯(lián)的懸掛邊顏色的種類(lèi)，而與u1、u2、u3、u4關(guān)聯(lián)的懸掛邊的條數(shù)不僅僅只有圖中出現(xiàn)的條數(shù)．后面再出現(xiàn)時(shí)，不再作注解．

在這種情況下，可按圖4所給出的9種方式進(jìn)行染色．

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

圖4 情況(2)的示意圖

Fig.4 The schematic graph of case (2)

情形(a)記為情形(1，1，1，12)，情形(b)記為情形(1，1，1，23)，其他類(lèi)似．除上述9種情形外，還有情形(12，2，2，2)等價(jià)于情形(a)；情形(12，3，3，3)等價(jià)于情形(b)；情形(1，1，23，3)、(1，12，3，3)和(1，1，23，3)等價(jià)于情形(c)；情形(1，2，2，23)、(1，1，23，4)、(1，23，4，4)、(12，3，3，4)和(12，3，4，4)等價(jià)于情形(d)；情形(1，12，2，2)等價(jià)于情形(g)；情形(1，2，2，23)、(1，23，3，3)和(12，2，2，3)等價(jià)于情形(i)；情形(1，2，23，4)、(1，2，34，4)、(1，12，3，4)、(1，23，3，4)和(12，2，3，4)等價(jià)于情形(e)；情形(1，2，34，5)、(1，23，4，5)和(12，3，4，5)等價(jià)于情形(f)；情形(1，2，23，3)等價(jià)于情形(h)．因此，出現(xiàn)的這些情形將不再畫(huà)圖表示．

由懸掛邊染色規(guī)律得，Au3≠Au4，則Au4Au3≠?且Au3Au4≠?．設(shè)a，b∈Au3且a

由懸掛邊染色規(guī)律得，Au2≠Au4，則Au4Au2≠?且Au2Au4≠?．設(shè)a，b∈Au2且a

這時(shí)由懸掛邊染色規(guī)律得，Au2、Au3、Au4互不相同．設(shè)Au1={c0}，a，b∈Au4，且a

下面用c0染u1u4；用k-1染u1；用k分別去染u1u2、u2、u2u3、u3和u3u4；用{1，2，…，k}{c0，a，b}中某種顏色去染u4．在上述染色下，c0?Cf(u3)，而c0∈Cf(u1)∩Cf(u4)，故Cf(u3)≠Cf(ui)，i=1，4；Au2≠Au3，k?Au2∪Au3，故Cf(u2)≠Cf(u3)；|Cf(u1)|=3，|Cf(u4)|≥4，故Cf(u1)≠Cf(u4)；k-1∈Cf(u1)Cf(u2)，故Cf(u1)≠Cf(u2)；a∈Cf(u4)Cf(u2)，故Cf(u2)≠Cf(u4)．因此，所得的染色是C4；m1，m2，m3，m4的k-GVDTC．

這時(shí)由懸掛邊染色規(guī)律得，Au1、Au3、Au4互不相同．設(shè)Au2={c0}，a，b∈Au1，且a

這時(shí)由懸掛邊染色規(guī)律得，Au1、Au2、Au4互不相同．設(shè)Au3={c0}，d0∈Au1，a，b∈Au4，且a

下面用k-1染u3；用k分別去染u1、u1u2、u2、u2u3和u3u4；用d0染u1u4；用{1，2，…，k}{a，b，d0}中某種顏色去染u4．可以看出，上述染色是C4；m1，m2，m3，m4的k-GVDTC．

這時(shí)由懸掛邊染色規(guī)律得，Au1、Au2、Au3互不相同．設(shè)Au4={c0}，d0∈Au1，a，b∈Au3，且a

下面用a染u4；用k分別去染u1、u1u2、u2和u2u3；用d0染u3u4與u1u4；用{1，2，…，k}{a，b，d0}中某種顏色去染u3．可以看出，上述染色是C4；m1，m2，m3，m4的k-GVDTC．

由懸掛邊染色規(guī)律得，Au1、Au2、Au3、Au4互不相同．設(shè)a，b∈Au1且a

在上述染色下，a∈Cf(u1)∩Cf(u4)，而a?Cf(u2)∩Cf(u3)，|Cf(ui)|≥3，i=1，2，3，4，故Cf(ui)≠Cf(uj)，j=1，4，i=2,3；c?Cf(u1)，而c∈Cf(u4)，故Cf(u1)≠Cf(u4)；Au2≠Au3，k?Au2∪Au3，故Cf(u2)≠Cf(u3)．因此，所得的染色是C4；m1，m2，m3，m4的k-GVDTC．

綜上即得C4；m1，m2，m3，m4的k-GVDTCf．

3 結(jié) 語(yǔ)

在本文定理1中，通過(guò)探討一類(lèi)含有4-圈的單圈圖的一般點(diǎn)可區(qū)別全染色，證明了它具有一般點(diǎn)可區(qū)別全染色，并得到了它的一般點(diǎn)可區(qū)別全色數(shù)．另外，一類(lèi)含有4-圈的單圈圖是通過(guò)在4-圈的基礎(chǔ)上加懸掛點(diǎn)得到的，那么這種方法是不是可以繼續(xù)延續(xù)下去，進(jìn)而得到一類(lèi)含有n-圈的單圈圖(n≥5)的一般點(diǎn)可區(qū)別全色數(shù)?這就是今后需要繼續(xù)研究的課題．

[1] HARARY F, PLANTHOLT M. The point-distinguishing chromatic index [M] // HARARY F, MAYBEE J S, eds. Graphs and Application. New York: Wiley Interscience, 1985:147-162.

[5] CHEN Xiang′en, GAO Yuping, YAO Bing. Vertex-distinguishing IE-total colorings of complete bipartite graphsKm,n(m

[6] LIU Chanjuan, ZHU Enqiang. General vertex-distinguishing total colorings of graphs [J]. Journal of Applied Mathematics, 2014, 2014:849748.

General vertex-distinguishing total colorings of a family of unicyclic graphs includingC4

CHEN Xiang′en*1， LI Ting1， WANG Zhiwen2

( 1.College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China；2.School of Mathematics and Computer Sciences, Ningxia University, Yinchuan 750021, China )

LetGbe a simple graph. For a general total coloringfofG, ifC(u)≠C(v) for any two different verticesuandvofG, thenfis called a general vertex-distinguishing total coloring ofG(or GVDTC ofGfor short). The minimum number of colors required in a GVDTC is the general vertex-distinguishing total chromatic number. The general vertex-distinguishing total colorings of a family of unicyclic graphs includingC4are discussed by making the coloring of its pendent edges in an ascending order. It is determined that it has a general vertex-distinguishing total coloring ofGand its general vertex-distinguishing total chromatic number is got.

unicyclic graphs; general total coloring; general vertex-distinguishing total coloring; general vertex-distinguishing total chromatic number

1000-8608(2017)03-0316-05

2016-06-15；

2017-02-23．

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163037，61163054，11261046)；寧夏回族自治區(qū)百人計(jì)劃資助項(xiàng)目.

陳祥恩*(1965-)，男，教授，E-mail:chenxe@nwnu.edu.cn；李 婷(1993-)，女，碩士生，E-mail:LTKR2016@126.com.

O157.5

A

10.7511/dllgxb201703015