• •

一类稀疏图的邻和可区别边色数

1. 1.河北工业大学理学院, 天津 300401;2.河北省大数据计算重点实验室, 天津 300401
• 收稿日期:2016-07-11 出版日期:2017-08-20 发布日期:2017-08-03
• 通讯作者: 徐常青(1970— ), 女, 教授, 硕士生导师, 研究方向为图论. E-mail:chqxu@hebut.edu.cn E-mail:whpkxkl@163.com
• 作者简介:潘文华(1989— ), 女, 硕士研究生, 研究方向为图论. E-mail:whpkxkl@163.com
• 基金资助:
国家自然科学基金资助项目(11671232,11301134,11301135);河北省自然科学基金资助项目(A2015202301);河北省高等学校科学技术研究重点项目(ZD2015106)

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.

• 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] 张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报（理学版）, 2018, 53(6): 7-10. [2] 姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2015, 50(02): 9-13. [3] 雒金梅,左连翠*. 关于图的L(2,1)-标号的岛序列[J]. J4, 2011, 46(6): 49-52. [4] 张欣1,徐兰2，刘桂真1. 稀疏图的k-森林染色[J]. J4, 2011, 46(4): 1-3.
Viewed
Full text

Abstract

Cited

Shared
Discussed