JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (8): 94-99.doi: 10.6040/j.issn.1671-9352.0.2016.326

Previous Articles     Next Articles

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.

Key words: maximum average degree, neighbor sum distinguishing edge coloring, sparse graph

CLC Number: 

  • O157
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: North-Holland, 1976.
[2] ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Appl Math Lett, 2002, 15(5):623-626.
[3] 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.
[4] 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.
[5] WANG Weifan, WANG Yiqiao. Adjacent vertex-distinguishing edge colorings of K4-minor free graphs[J]. Appl Math Lett, 2011, 24(12):2034-2037.
[6] HUANG Danjun, MIAO Zhengke, WANG Weifan. Adjacent vertex distinguishing indices of planar graphs without 3-cycles[J]. Discrete Math, 2015, 338(3):139-148.
[7] FLANDRIN E, MARCZYK A, PRZYBYŁO J, et al. Neighbor sum distinguishing index[J]. Graphs and Combin, 2013, 29(5):1329-1336.
[8] WANG Guanghui, YAN Guiying. An improved upper bound for the neighbor sum disthinguishing index of graphs[J]. Discrete Appl Math, 2014, 175:126-128.
[9] DONG Aijun, WANG Guanghui. Neighbor sum distinguishing coloring of some graphs[J]. Discrete Math Algorithms Appl, 2012, 4(4):1250047(12 pages).
[10] WANG Guanghui, CHEN Zhumin, WANG Jihui. Neighbor sum distinguishing index of planar graphs[J]. Discrete Math, 2014, 334:70-73.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] Alon N. Combinatorial Nullstellensatz[J]. Combin Probab Comput, 1999, 8(1/2):7-29.
[1] 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.
[2] 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.
[3] LUO Jin-mei, ZUO Lian-cui*. On the island sequences of L(2,1)-labeling of graphs [J]. J4, 2011, 46(6): 49-52.
[4] 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!