齒輪圖的鄰點(diǎn)強(qiáng)可區(qū)別的全染色

張東翰，李 超

(商洛學(xué)院數(shù)學(xué)與計算機(jī)應(yīng)用學(xué)院，726000，陜西，商洛)

齒輪圖的鄰點(diǎn)強(qiáng)可區(qū)別的全染色

張東翰，李 超

(商洛學(xué)院數(shù)學(xué)與計算機(jī)應(yīng)用學(xué)院，726000，陜西，商洛)

齒輪圖；鄰點(diǎn)強(qiáng)可區(qū)別的全染色；鄰點(diǎn)強(qiáng)可區(qū)別的全色數(shù)

0 引言

1 預(yù)備知識

定義1[7]：設(shè)G(V,E)是階數(shù)不小于3的簡單連通圖，k是自然數(shù)，f是從V(G)∪E(G)到{1,2…k}的映射，如果滿足：

1)對任意的邊uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v)；

2)對任意的兩相鄰的邊uv,uw∈E(G)(v≠w),f(uv)≠f(uw)；

3)對任意的邊uv∈E(G)，其端點(diǎn)的色集合滿足C(u)≠C(v)，其中任一頂點(diǎn)u的色集合為C(u)={f(u)}∪{f(v)|uv∈E(G)}∪{f(uv)|uv∈E(G)}。

則稱f是圖G的一個鄰點(diǎn)強(qiáng)可區(qū)別的全染色法(簡記作k-AVSDTC)，且稱數(shù)χast(G)=min{k|G存在k-AVSDTC}為G的鄰點(diǎn)強(qiáng)可區(qū)別的全色數(shù)。

引理1[7]：設(shè)圖G是階數(shù)不小于3的圖，有χast(G)≥△+1；若G有相鄰的2個最大度點(diǎn)，則有χast(G)≥△+2，其中△代表圖G的最大度。

本文中未加敘述的術(shù)語、記號可在文獻(xiàn)[9-11]中找到。

2 定理及其證明

綜上可知，定理2成立。

[1]Zhang Zhongfu,Zhang Jianxun,Wang Jianfang,The total chromatic number of some graphs[J].Science Sinica Ser A:1434-1441.

[2]張東翰.蛛形圖的全染色和星全染色[J].商洛學(xué)院學(xué)報,2013,27(6):31-32.

[3]李曉東.圖全染色的幾個定理[J].哈爾濱理工大學(xué)學(xué)報,2001,6(1):100-102.

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

[5]張東翰,王曉.路的廣義Mycielski圖的鄰點(diǎn)可區(qū)別的全染色[J].蘭州理工大學(xué)學(xué)報,2009,35(5):146-147.

[6]陳祥恩,張忠輔.Pm∨Pn的鄰點(diǎn)可區(qū)別的全染色[J].西北師范大學(xué)學(xué)報,2005,41(1):13-15.

[7]張忠輔,程輝,姚兵.圖的鄰點(diǎn)強(qiáng)可區(qū)別的全染色[J].中國科學(xué):A輯,2007,37(9):1073-1082.

[9]張東翰,朱白.路的D(3)-點(diǎn)可區(qū)別的全染色[J].商

洛學(xué)院學(xué)報,2014,28(2):11-12.

[10]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:The Macmillan Press Ltd,1976.

[11]Reinhard D.Graph Theory[M].New York:Springer-Verlag,1997.

TheAdjacent-Vertex-Strongly-DistinguishingTotalColouringoftheGearGraph

ZHANG Donghan,LI Chao

(College of Mathematics and Computer Applications,Shangluo University,726000,Shangluo,Shanxi,PRC)

the gear graph;the adjacent vertex strongly distinguishing total colouring;the adjacent vertex strongly distinguishing total chromatic number

2014-05-21;

2014-06-23

張東翰(1981-)，男，河北邢臺人，碩士，講師，研究方向：圖論及其應(yīng)用。

陜西省自然科學(xué)基礎(chǔ)研究計劃項目(2013JM1023)；陜西普通本科高等學(xué)校教學(xué)改革研究重點(diǎn)資助項目(13BZ56)；陜西省教育廳科研計劃基金項目(14JK1225)；商洛學(xué)院教育教學(xué)改革研究項目(14JYJX133)。

10.13990/j.issn1001-3679.2014.04.015

O157.5

A

1001-3679(2014)04-0493-03