胡鳳鳳，劉家保

(1．安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，合肥 230601;2．安徽新華學(xué)院公共課教學(xué)部，合肥 230088)

關(guān)于一類圖的鄰點(diǎn)可區(qū)別全染色*

胡鳳鳳1，劉家保2

(1．安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，合肥 230601;2．安徽新華學(xué)院公共課教學(xué)部，合肥 230088)

圖G的一個(gè)正常全染色f稱為是鄰點(diǎn)可區(qū)別的，如果G中任何相鄰點(diǎn)及其關(guān)聯(lián)邊的顏色集合不同;對(duì)一個(gè)圖G進(jìn)行鄰點(diǎn)可區(qū)別的正常全染色所用最少顏色數(shù)稱為G的鄰點(diǎn)可區(qū)別全色數(shù)，記為 χat(G);給出了一類特殊圖類的鄰點(diǎn)可區(qū)別全色數(shù)．

正常全染色;鄰點(diǎn)可區(qū)別全染色;鄰點(diǎn)可區(qū)別全色數(shù)

具有重要實(shí)際意義和理論意義的圖的染色問(wèn)題，是圖論的主要研究?jī)?nèi)容之一．隨著圖的染色問(wèn)題在現(xiàn)實(shí)中被廣泛應(yīng)用，它逐漸成為眾多學(xué)者研究的重要領(lǐng)域之一．起源于網(wǎng)絡(luò)問(wèn)題、生物學(xué)、信息科學(xué)、計(jì)算機(jī)科學(xué)的點(diǎn)可區(qū)別邊染色或強(qiáng)邊染色是一個(gè)十分困難的問(wèn)題．在文獻(xiàn)［1，2］中，點(diǎn)可區(qū)別邊染色和鄰點(diǎn)可區(qū)別邊染色問(wèn)題得到進(jìn)一步研究．張忠輔教授在文獻(xiàn)［3］中提出鄰點(diǎn)可區(qū)別全染色的概念．新的染色問(wèn)題不斷被提出，與該問(wèn)題相關(guān)的文獻(xiàn)［3－9］中給出了鄰點(diǎn)可區(qū)別染色、鄰點(diǎn)可區(qū)別強(qiáng)全染色等染色的定義及其幾類簡(jiǎn)單圖關(guān)于此染色的色數(shù)，并提出了一些猜想．此處所考慮的圖都是有限簡(jiǎn)單無(wú)向圖，用V(G)，E(G)分別表示圖G的頂點(diǎn)集、邊集，Δ(G)表示圖G的最大度，所用的未說(shuō)明的圖論術(shù)語(yǔ)與記號(hào)參見(jiàn)文獻(xiàn)［9］．

1 相關(guān)定義

定義1［3］設(shè)圖G是階至少為2的連通圖，k是正整數(shù)，f是V(G)∪E(G)到{1，2，…，k}的映射，?u，v∈V(G)，記C(u)={f(u)}∪{f(uv)|u，v∈V(G)，uv∈E(G)}．

如果對(duì)?uv，vw∈E(G)，u≠w，有f(uv)≠f(vw);對(duì)任意uv∈E(G)，有f(u)≠f(v)，f(u)≠f(uv)，f(v)≠f(uv)，則稱f為圖G的k－正常全染色;進(jìn)一步，如果f還滿足對(duì)任意uv∈E(G)，有C(u)≠C(v)，則稱f為圖G的k－鄰點(diǎn)可區(qū)別全染色(簡(jiǎn)記為k－AVDTC)，稱min{k|G有k－鄰點(diǎn)可區(qū)別全染色}為圖G的鄰點(diǎn)可區(qū)別全色數(shù)，記為χat(G)，其中C(u)稱為點(diǎn)u在f下的色集合．

定義2［10］設(shè)圖是由長(zhǎng)為h的路連接一個(gè)m星圖中心和一個(gè)n星圖的中心所得到的圖，其中:

2 引 理

引理1 若G有兩個(gè)相鄰的最大度頂點(diǎn)，則

證明 設(shè)u，v是G中相鄰的兩個(gè)最大度頂點(diǎn)，則對(duì)于G的任意一個(gè)k－鄰點(diǎn)可區(qū)別全染色f來(lái)說(shuō)，C(u)和C(v)均有Δ(G)+1種顏色，而C(u)≠C(v)，因此要使G有k－鄰點(diǎn)可區(qū)別全染色，必有k≥Δ(G)+2，故結(jié)論成立．

引理2［4］設(shè)Pn是n階的路，n≥2，則

引理3［4］設(shè)Cn表示n階圈，則

引理4［4］對(duì)于n+1階星Sn(n≥3)，有χat(Sn)=n+1．

3 主要結(jié)論及其證明

當(dāng)m≠n時(shí)，有

證明 分兩種情況來(lái)加以討論說(shuō)明．

情況Ⅰ 1)當(dāng)m=n=1，h=2時(shí)，圖Thm，n就是一條4階路，由引理2可知χaT=4．

2)當(dāng)m=n且h是奇數(shù)時(shí)，定義一個(gè)從V(Thm，n)∪E(Thm，n)到{0，1，2，…，Δ(Thm，n)+2}上的映射f如下:

3)當(dāng)m=n且h是偶數(shù)時(shí)，定義一個(gè)從V(Thm，n)∪E(Thm，n)到{0，1，2，…，Δ(Thm，n)+1}上的映射f如下:

情況Ⅱ 1)當(dāng)m=1，n≠1(或 m≠1，n=1)時(shí)，定義一個(gè)從到{0，1，2，…，的映射f如下:

［1］BALISTER P N，BOLLOB B，SHELP R H．Vertex Distinguishing Coloring of Graphs with Δ(G)=2［J］．Discrete Mathematics，2002(252):17-29

［2］ZHANG Z F，LIU L ZH，WANG J F．Asjacent Strong Edge Coloring of Graphs［J］．Applied Mathematics Letters，2002(15): 623-626

［3］ZHANG Z F．On the Adjacent Vertex Distinguish Total Coloring of Graphs［J］．Science in China Ser A，2004(10):574-583

［4］劉家保，王林，陸一南．雙圈圖G(n，m)的奇優(yōu)美標(biāo)號(hào)及其算法［J］．合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2012，35(5): 708-710

［5］劉家保，王林，陸一南．具有公共邊的雙圈圖的奇優(yōu)美標(biāo)號(hào)及其算法［J］．合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2012，35(6): 857-859

［6］張忠輔，李敬文，陳樣恩．圖的距離不超過(guò)β的點(diǎn)可區(qū)別全染色［J］．中國(guó)科學(xué)A輯:數(shù)學(xué)，2006，36(10):1119-1130

［7］劉家保，鄒婷，陸一南．關(guān)于笛卡爾乘積圖的優(yōu)美性［J］．純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2012，28(3):329-332

［8］嚴(yán)謙泰．關(guān)于圖的一般鄰點(diǎn)可區(qū)別全染色［J］．系統(tǒng)科學(xué)與數(shù)學(xué)，2010(1):101-106

［9］BONDY J A，MURTY U S R．Graph Theory with Applications［M］．New York:American Elsevier，1976

［10］劉家保，呂寧寧，余國(guó)鋒．關(guān)于一類樹的優(yōu)美標(biāo)號(hào)［J］．河北北方學(xué)院學(xué)報(bào):自然科學(xué)版，2010，26(5):1-4

On Adjacent Vertex Distinguishing Total Coloring for a Class of Graphs

HU Feng-feng1，LIU Jia-bao2
(1．School of Mathematical Science，Anhui University，Hefei 230601，China; 2．Teaching Department for Common Courses，Anhui Xinhua University，Hefei 230088，China)

A normal total coloring f of graph G is adjacent vertex distinguishing．If any point of an adjacent vertex in G and the color set of its related edges are different，the smallest number of colors used in the normal adjacent vertex distinguishing total coloring for a Graph G is called the number of adjacent vertex distinguishing total coloring and is denoted as Xat(G)．This paper gives a class of special adjacent vertex distinguishing total coloring number of graphs．

normal total coloring;adjacent vertex distinguishing total coloring;adjacent vertex distinguishing total coloring number

O157．5

A

1672－058X(2015)02－0023－04

10．16055/j．issn．1672－058X．2015．0002．005

責(zé)任編輯:李翠薇

2014－07－18;

2014－09－18．

安徽省高等學(xué)校省級(jí)自然科學(xué)基金項(xiàng)目(KJ2010B105);安徽新華學(xué)院質(zhì)量工程建設(shè)項(xiàng)目(2012tskcx04，2012tskcx05)．

胡鳳鳳(1990-)，女，安徽蚌埠人，碩士研究生，從事圖論與組合網(wǎng)絡(luò)研究．