胡鳳鳳，劉家保

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

關于一類圖的鄰點可區(qū)別全染色*

胡鳳鳳1，劉家保2

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

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

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

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

1 相關定義

定義1［3］設圖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)}．

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

定義2［10］設圖是由長為h的路連接一個m星圖中心和一個n星圖的中心所得到的圖，其中:

2 引 理

引理1 若G有兩個相鄰的最大度頂點，則

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

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

引理3［4］設Cn表示n階圈，則

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

3 主要結論及其證明

當m≠n時，有

證明 分兩種情況來加以討論說明．

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

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

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

情況Ⅱ 1)當m=1，n≠1(或 m≠1，n=1)時，定義一個從到{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)美標號及其算法［J］．合肥工業(yè)大學學報:自然科學版，2012，35(5): 708-710

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

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

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

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

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

［10］劉家保，呂寧寧，余國鋒．關于一類樹的優(yōu)美標號［J］．河北北方學院學報:自然科學版，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

責任編輯:李翠薇

2014－07－18;

2014－09－18．

安徽省高等學校省級自然科學基金項目(KJ2010B105);安徽新華學院質量工程建設項目(2012tskcx04，2012tskcx05)．

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