魏邦魁，強(qiáng)會(huì)英，顧忠棟

（蘭州交通大學(xué) 數(shù)學(xué)院，甘肅 蘭州 730070）

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

魏邦魁，強(qiáng)會(huì)英，顧忠棟

（蘭州交通大學(xué) 數(shù)學(xué)院，甘肅 蘭州 730070）

運(yùn)用分析法和窮舉法，研究了路，圈，星，扇，輪的三倍圖的鄰點(diǎn)可區(qū)別E-全染色，并且得到了他們的鄰點(diǎn)可區(qū)別E-全色數(shù)。

三倍圖；鄰點(diǎn)可區(qū)別E-全染色；鄰點(diǎn)可區(qū)別E-全色數(shù)

1 引言

圖的染色是圖論的重要研究之一在近年來許多的圖論理論研究者們提出了一系列的新的染色問題，如：點(diǎn)可區(qū)別全染色，鄰點(diǎn)可區(qū)別全染色，以及鄰點(diǎn)可區(qū)別E-全染色，本文主要研究了三倍圖（路，圈，星，扇，輪）的鄰點(diǎn)可區(qū)別E-全色數(shù)。

定義1[1,2]對(duì)一個(gè)簡(jiǎn)單圖G（V,E），k為正整數(shù)，映射f滿足：

則稱為f為圖G的鄰點(diǎn)可區(qū)別E-全染色，簡(jiǎn)記為k-AVDETC 。記

為圖G的鄰點(diǎn)可區(qū)別E-全色數(shù)，其中

定義2[3]對(duì)于簡(jiǎn)單圖G，如果

則稱T（G）為簡(jiǎn)單圖G的三倍圖。其中圖G'，G''是圖G的拷貝。

引理[4]對(duì)于簡(jiǎn)單圖G，當(dāng)E（ G）≠，則（G）存在，并且（G）≥3。

圖中未加說明的符號(hào)或術(shù)語，可參看文獻(xiàn)[5]。

2 主要結(jié)論

證明由引理知

定理1 對(duì)于n階路Pn，n≥3有

為證明

僅給出T（Pn）的一個(gè)3-AVDETC。下面定義一個(gè)

[1] 張威,張荔,李沐春.輪與路的多重聯(lián)圖的鄰點(diǎn)可區(qū)別E-全染色[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2012,42(10):128-132.

[2] 李沐春,張忠輔.若干聯(lián)圖的鄰點(diǎn)可區(qū)別E-全染色[J].西北師范大學(xué)學(xué)報(bào),2009,45(1):24-26.

[3] 文飛,張玉紅,朱恩強(qiáng).關(guān)于若干倍圖的鄰點(diǎn)可區(qū)別邊全染色[J].天水師范學(xué)院學(xué)報(bào),2009,29(2):6-8.

[4] Zhang Zhong-fu, Qiu Peng-xiang, et al. Vertex-distinguishing total coloring of graphs[J]. Ars Combinatoria, 2008, 87: 33-45.

[5] 邦迪J A,默蒂U S R.圖論及其應(yīng)用[M].科學(xué)出版社,1976: 12-45.

（責(zé)任編輯、校對(duì)：趙光峰）

On Some Adjacent Vertex-Distinguishing Edge Total Coloring
of Triple Graphs

WEI Bang-kui, QIANG Hui-ying, GU Zhong-dong
(School of Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, China)

Using the analysis method and its adjacent vertex distinguishing edge total coloring function method to study the adjacent vertex-distinguishing edge total coloring of the triple graph of path, circle, star, fan and wheel we got the adjacent vertex-distinguishing edge total chromatic number of them.

triple graph; vertex-distinguishing edge total chromatic number; adjacent vertex-distinguishing edge total coloring

O157.5

A

1009-9115(2016)02-0011-03

10.3969/j.issn.1009-9115.2016.02.003

2015-10-10

魏邦魁（1988-），男，甘肅蘭州人，碩士研究生，研究方向?yàn)閳D論及其應(yīng)用。