JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (04): 63-66.doi: 10.6040/j.issn.1671-9352.0.2014.327

Previous Articles     Next Articles

Adjacent vertex-distinguishing edge/total colorings of double graph of some graphs

HE Xue, TIAN Shuang-liang   

  1. School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, Gansu, China
  • Received:2014-07-15 Revised:2015-03-05 Online:2015-04-20 Published:2015-04-17

PDF (PC)

1032

Abstract: Let G be a simple graph with vertex set V(G) and edge set E(G). An edge-coloring σ of G is called an adjacent vertex distinguishing edge-coloring of G if Cσ(u)≠Cσ(v) for any uv∈E(G), where Cσ(u) denotes the set of colors of edges incident with u. A total-coloring σ of G is called an adjacent vertex distinguishing total-coloring of G if Sσ(u)≠Sσ(v) for any uv∈E(G), where Sσ(u) denotes the set of colors of edges incident with u together with the color assigned to u. The minimum number of colors required for an adjacent vertex-distinguishing edge-coloring (resp. total-coloring) of G is called adjacent vertex-distinguishing edge (resp. total) chromatic number, and denoted by χ'as(G) (resp. χat(G)). The upper bounds for these parameters of the double graph D(G) of graph G are given in this paper. Specifically, the exact value of these parameters for the double graph of complete graphs and trees are determined.

Key words: double graph, adjacent vertex-distinguishing edge coloring, adjacent vertex-distinguishing total coloring

CLC Number: 

  • O157.5
[1] ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15:623-626.
[2] 张忠辅, 陈祥恩, 李敬文,等. 关于图的邻点可区别全染色[J]. 中国科学:A辑, 2005, 48(3):289-299. ZHANG Zhongfu, CHEN Xiang'en, LI Jingwen, et al. On adjacent-vertex-distinguishing total coloring of graphs[J]. Science in China: Ser. A, 2005, 48(3):289-299.
[3] 张忠辅, 仇鹏翔, 张东翰,等. 图的倍图与补倍图[J]. 数学进展, 2008, 37(3):303-310. ZHANG Zhongfu, QIU Pengxiang, ZHANG Donghan, et al. The double graph and the complement double graph of a graph[J]. Advances in Mathematics, 2008, 37(3):303-310.
[4] BALISTER P N, GYÖRI E, LEHEL J, et al. Adjacent vertex distinguishing edge-colorings[J]. SIAM J. Discrete Math, 2007, 21(1):237-250.
[5] TIAN Shuangliang, CHEN Ping, SHAO Yabin, et al. Adjacent vertex distinguishing edge-colorings and total-colorings of the cartesian product of graphs[J]. Control and Optimization, 2014, 4(1):49-58.
[6] CHEN Xiang'en, ZHANG Zhongfu. Adjacent vertex distinguishing total chromatic number of Pm×Kn[J]. Journal of Mathematical Research and Exposition, 2006, 26(3):489-494.
[7] BARIL J-L, KHEDDOUCI H, TOGNI O. Adjacent vertex distinguishing edge-colorings of meshes and hypercubes[J]. Australasian Journal of Combinatorics, 2006, 35:89-102.
[8] CHEN Meirun, GUO Xiaofeng. Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes[J]. Information Processing Letters, 2009, 109:599-602.
[9] 田双亮, 陈萍. 两类积图的邻点可区别全染色[J]. 数学研究与评论, 2007, 27(4):733-737. TIAN Shuangliang, CHEN Ping. On the adjacent vertex-distinguishing total coloring of two classes of product graph[J]. Journal of Mathematical Research and Exposition, 2007, 27(4):733-737.
[10] 田京京, 杨立夫, 王树勋,等. 扇的倍图的邻点可区别边色数[J]. 数学的实践与认识, 2008, 38(15):221-224. TIAN Jingjing, YANG Lifu, WANG Shuxun, et al. The chromatic number of adjacent-strong edge coloring of the double graph D(Fm)[J]. Mathematics in Practice and Theory, 2008, 38(15):221-224.
[11] 苏旺辉, 刘永平, 谢继国,等. 完全图的倍图的邻点可区别全染色[J]. 兰州理工大学学报, 2008, 34(3):166-167. SU Wanghui, LIU Yongping, XIE Jiguo, et al. Distinguishable total coloring of adjacent vertex of doubled complete graphs[J]. Journal of Lanzhou University of Technology, 2008, 34(3):166-167.
[12] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: American Elsevier, 1976.
[13] YAP H P. Total Coloring of graph[M]. New York: Springer Verlag, 1996.
[1] WEN Fei1, WANG Zhi-wen2, WANG Hong-jie3, BAO Shi-tang4, LI Mu-chun1*, ZHANG Zhong-fu1. Vertex-distinguishing total coloring of some complement double graphs [J]. J4, 2011, 46(2): 45-50.
[2] . On the Smarandachelyadjacentvertex edge coloring of some double graphs [J]. J4, 2009, 44(12): 25-29.
[3] TIAN Shuang-liang . On the adjacent vertex-distinguishing total coloring of some generalized Petersen graphs [J]. J4, 2008, 43(9): 42-44 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd