### Neighbor sum distinguishing index of a kind of sparse graphs

PAN Wen-hua1, XU Chang-qing1,2*

1. 1. School of Science, Hebei University of Technology, Tianjin 300401, China;
2. Hebei Province Key Laboratory of Big Data Calculation, Tianjin 300401, China
• Received:2016-07-11 Online:2017-08-20 Published:2017-08-03

Abstract: Let φ be a proper k-edge coloring of G. For each vertex v∈V(G), set fφ(v)=∑uv∈E(G)φ(uv). φ is called a k-neighbor sum distinguishing edge coloring of G if fφ(u)≠fφ(v) for each edge uv∈E(G). The smallest k such that G has a k-neighbor sum distinguishing edge coloring is called the neighbor sum distinguishing index, denoted by χ'Σ(G). The neighbor sum distinguishing index of a kind of sparse graphs is determined. It is proved that if G is a graph without isolated edges, Δ≥6 and mad(G)≤5/2, then χ'Σ(G)=Δ if and only if G has no adjacent vertices of maximum degree.

CLC Number:

• O157
  BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: North-Holland, 1976. ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Appl Math Lett, 2002, 15(5):623-626. WANG Weifan, WANG Yiqiao. Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree[J]. J Comb Optim, 2010, 19(4):471-485. WANG Yi, CHENG Jian, LUO Rong, et al. Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs[J]. J Comb Optim, 2016, 31(2):874-880. WANG Weifan, WANG Yiqiao. Adjacent vertex-distinguishing edge colorings of K4-minor free graphs[J]. Appl Math Lett, 2011, 24(12):2034-2037. HUANG Danjun, MIAO Zhengke, WANG Weifan. Adjacent vertex distinguishing indices of planar graphs without 3-cycles[J]. Discrete Math, 2015, 338(3):139-148. FLANDRIN E, MARCZYK A, PRZYBYŁO J, et al. Neighbor sum distinguishing index[J]. Graphs and Combin, 2013, 29(5):1329-1336. WANG Guanghui, YAN Guiying. An improved upper bound for the neighbor sum disthinguishing index of graphs[J]. Discrete Appl Math, 2014, 175:126-128. DONG Aijun, WANG Guanghui. Neighbor sum distinguishing coloring of some graphs[J]. Discrete Math Algorithms Appl, 2012, 4(4):1250047(12 pages). WANG Guanghui, CHEN Zhumin, WANG Jihui. Neighbor sum distinguishing index of planar graphs[J]. Discrete Math, 2014, 334:70-73. DONG Aijun, WANG Guanghui, ZHANG Jianghua. Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree[J]. Discrete Appl Math, 2014, 166:84-90. GAO Yuping, WANG Guanghui, WU Jianliang. Neighbor sum distinguishing edge colorings of graphs with small maximum average degree[J]. Bull Malays Math Sci Soc, 2016, 39(Supplement 1):247-256. YU Xiaowei, QU Cunquan, WANG Guanghui, et al. Adjacent vertex distinguishing colorings by sum of sparse graphs[J]. Discrete Math, 2016, 339(1):62-71. LI Hualong, DING Laihao, LIU Bingqiang, et al. Neighbor sum distinguishing total colorings of planar graphs[J]. J Comb Optim, 2015, 30(3):675-688. Alon N. Combinatorial Nullstellensatz[J]. Combin Probab Comput, 1999, 8(1/2):7-29.
  ZHANG Jiang-yue, XU Chang-qing. Linear 2-arboricity of graphs with maximum average degree at most 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 7-10.  YAO Jing-jing, XU Chang-qing. Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 9-13.  LUO Jin-mei, ZUO Lian-cui*. On the island sequences of L(2,1)-labeling of graphs [J]. J4, 2011, 46(6): 49-52.  ZHANG Xin1, XU Lan2, LIU Gui-Zhen1. k-forested coloring of sparse graphs [J]. J4, 2011, 46(4): 1-3.
Viewed
Full text

Abstract

Cited

Shared
Discussed
 No Suggested Reading articles found!