魏邦魁,強會英,顧忠棟
(蘭州交通大學 數學院,甘肅 蘭州 730070)
關于一類三倍圖的鄰點可區別E-全染色
魏邦魁,強會英,顧忠棟
(蘭州交通大學 數學院,甘肅 蘭州 730070)
運用分析法和窮舉法,研究了路,圈,星,扇,輪的三倍圖的鄰點可區別E-全染色,并且得到了他們的鄰點可區別E-全色數。
三倍圖;鄰點可區別E-全染色;鄰點可區別E-全色數
圖的染色是圖論的重要研究之一在近年來許多的圖論理論研究者們提出了一系列的新的染色問題,如:點可區別全染色,鄰點可區別全染色,以及鄰點可區別E-全染色,本文主要研究了三倍圖(路,圈,星,扇,輪)的鄰點可區別E-全色數。
定義1[1,2]對一個簡單圖G(V,E),k為正整數,映射f滿足:
則稱為f為圖G的鄰點可區別E-全染色,簡記為k-AVDETC 。記
為圖G的鄰點可區別E-全色數,其中
定義2[3]對于簡單圖G,如果
則稱T(G)為簡單圖G的三倍圖。其中圖G',G''是圖G的拷貝。
引理[4]對于簡單圖G,當E( G)≠,則(G)存在,并且(G)≥3。
圖中未加說明的符號或術語,可參看文獻[5]。
證明由引理知
定理1 對于n階路Pn,n≥3有
為證明
僅給出T(Pn)的一個3-AVDETC。下面定義一個
[1] 張威,張荔,李沐春.輪與路的多重聯圖的鄰點可區別E-全染色[J].數學的實踐與認識,2012,42(10):128-132.
[2] 李沐春,張忠輔.若干聯圖的鄰點可區別E-全染色[J].西北師范大學學報,2009,45(1):24-26.
[3] 文飛,張玉紅,朱恩強.關于若干倍圖的鄰點可區別邊全染色[J].天水師范學院學報,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.圖論及其應用[M].科學出版社,1976: 12-45.
(責任編輯、校對:趙光峰)
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-),男,甘肅蘭州人,碩士研究生,研究方向為圖論及其應用。