楊隨義,王治文

一類3-正則圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色

楊隨義1,王治文2

(1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,甘肅天水741000; 2.寧夏大學(xué)數(shù)學(xué)計(jì)算機(jī)學(xué)院,寧夏銀川750021)

對簡單圖G(V,E),f是從V(G)∪E(G)到{1,2,…,k}的映射,k是自然數(shù),若f滿足(1)?uv∈E(G),u≠v,f(u)≠f(v);(2)?uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)?uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};則稱f是G的一個(gè)關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色.給出了一類3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2))的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù).

3-正則重圈圖;鄰點(diǎn)可區(qū)別全染色;關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù)

圖的染色是圖論的重要研究內(nèi)容之一,由計(jì)算機(jī)科學(xué)和信息科學(xué)等所產(chǎn)生的一般點(diǎn)可區(qū)別邊染色[1],鄰點(diǎn)可區(qū)別邊染色(或鄰強(qiáng)邊染色)[2-5]及D(β)點(diǎn)可區(qū)別邊染色[6],點(diǎn)可區(qū)別邊染色[7-8],鄰點(diǎn)可區(qū)別全染色[9]等都是十分困難的問題,至今文獻(xiàn)甚少.在此基礎(chǔ)之上,Zhang進(jìn)一步提出了新的染色概念,圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色是其中之一[9].本文給出了一類3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2))的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù).

定義1[9]對于階數(shù)不小于2的連通圖G(V,E),f是從V(G)∪E(G)到{1,2,…,k}的映射,k是自然數(shù),如果f滿足:

(1)?uv∈E(G),u≠v,有f(u)≠f(v);

(2)?uv,uw∈E(G),v≠w,f(uv)≠f(uw);

(3)?uv∈E(G),C(u)≠C(v);

其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};則稱f是圖G的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色,也稱G有k-關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色.(簡記作k-I-AVD TC),記為G的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù).

定義2[10]設(shè)G(V,E)是簡單圖,如果m≥2,n≥3且

猜想1[9]對簡單圖G,則有χiat(G)≤Δ+2,其中Δ是G的最大度.

文中未加說明的術(shù)語、記號(hào)可參看文獻(xiàn)[11,12].

1 主要結(jié)論

定理 對于3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2)),則有

證明 由定義1知,χiat(Re(n,m))≥4,為證明χiat(Re(n,m))=4,僅需給出3-正則重圈圖Re(n,m)的一個(gè)4-I-AVD TC.如下定義一個(gè)從V(Re(n,m))∪E(Re(n,m))到{1,2,3,4}的映射f:

情況1 若m=2,3時(shí),易證χiat(Re(n,m))=4(n≥3且n≡0(mod2))成立.

情況2 當(dāng)m≥4時(shí),

在下述證明中當(dāng)j+1>2n時(shí)j+1(mod2n).由于各層分布與m的值有關(guān),所以按m進(jìn)行如下分類:情況2.1當(dāng)m≡0(mod4)時(shí),

情況2.2 當(dāng)m≡3(mod4)時(shí),

此時(shí)

情況2.3 當(dāng)m≡1(mod4)或m≡2(mod4)時(shí),類似于情況2.1,2.2證明.

綜上可知,f是3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2))的一個(gè)4-I-AVD TC.

[1] BURRIS A C,SCHELP R H.Vertex-distinguishing Proper Edge-coloring[J].J Graph Theory,1997,26(2):73-82.

[2] BALISTER P N,GYORI E,L EHEL J,et al.Adjacent Vertex Distinguishing Edge-colorings[J].S IA MJ Discrete Math, 2007,21:237-250.

[3] HATAMI H.Δ+300 is a Bound on the Adjacent Vertex Distinguishing Edge Chromatic Number[J].J ournal of Combinatorial Theory,SeriesB,2005,95:246-256.

[4] ZHANG Z,LIU L,WANGJ.Adjacent Strong Edge Coloring of Graphs[J].A ppl Math Lett,2002,15:623-626.

[5] ZHANG Zhong-fu,LI J,CHEN X,et al.D(β)-vertex-distinguishing Proper Edge-coloring of Graphs[J].Acta Math Sinica(Chin Ser),2006,15:703-708.

[6] ZHANG Z,QIU P,XU B,et al.Vertex-distinguishing Total Coloring of Graphs[J].A rs Comb,2008,87:33-45.

[7] 張忠輔,李敬文,陳祥恩.圖的距離不大于β的點(diǎn)可區(qū)別的全染色[J].中國科學(xué),2006,49(10):1430-1440.

[8] ZHANG Z,CHEN X,LI J,et al.On Adjacent-vertex-distinguishing Total Coloring of Graphs[J].Sci Chins(S ER A), 2005,48(3):289-299.

[9] CHANG C(ZHANG Z),WOODALL D R.LIJ,et al.Incidence Adjacent Vertex-distinguishing Total Coloring of Graphs

[R].蘭州交通大學(xué)科學(xué)報(bào)告,2008,2:1-8.

[10] ZHANG Z.The Smarandachely Adjacent Vertex Total Coloring of Graphs[R].蘭州交通大學(xué)科學(xué)報(bào)告,2009,2-3.

[11] BONDYJ A,MURTY U S R.Graph Theory with Applications[M].London:Macmillan;New York:Elsever,1986.

[12] 王治文,徐保根,閆麗宏,等.關(guān)于圈的廣義Mycielski圖的全染色[J].山西大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,31(4):20-23.

Incidence Adjacent Vertex-distinguishing Total Coloring of a Kind of 3-regular Graph

YANG Sui-yi1,WANG Zhi-wen2
(1.College of Mathematics,Tianshui Normal University,Tianshui741000,China; 2.School of Mathematics and Computer Science,Ningxia University,Yinchuan750021,China)

LetGbe a simple graph andkbe a positive integer.Iffis a mapping fromV(G)∪E(G)to{1,2,…,k},such that(1)?uv∈E(G),u≠v,f(u)≠f(v);(2)?uv,vw∈E(G),u≠w,f(uv)≠f(vw);(3)?uv∈E(G),C(u)≠C(v),we say thatfis a incidence adjacent vertex-distinguishing total coloring ofG,where C(u)={f(u)}∪{f(uv)|uv∈E(G)}.The minimal number ofkis called as the incidence adjacent vertexdistinguishing total chromatic number ofG.The incidence adjacent vertex-distinguishing total chromatic number of 3-repeated cycle graph is disussed.

3-repeated cycle graph;incidence adjacent vertex-distinguishing total coloring;incidence adjacent vertex-distinguishing total chromatic number

O157.5

A

0253-2395(2010)03-0354-04

2009-11-01

國家自然科學(xué)基金(10771091);寧夏大學(xué)科學(xué)研究基金((E)ndzr09-15)

楊隨義(1977-),男,講師,主要從事代數(shù)圖論的研究.通訊作者王治文,E-mail:w.zhiwen@163.com