Neighbor sum distinguishing edge colorings of sparse graphs

被引:10
作者
Hu, Xiaolan [1 ]
Chen, Yaojun [1 ]
Luo, Rong [2 ]
Miao, Zhengke [3 ]
机构
[1] Nanjing Univ, Dept Math, Nanjing 210093, Jiangsu, Peoples R China
[2] W Virginia Univ, Dept Math, Morgantown, WV 26506 USA
[3] Jiangsu Normal Univ, Sch Math & Stat, Xuzhou 221116, Jiangsu, Peoples R China
基金
美国国家科学基金会;
关键词
Proper edge colorings; Neighbor sum distinguishing edge colorings; Maximum average degree; Maximum degree; DISTINGUISHING INDEX; PLANAR GRAPHS;
D O I
10.1016/j.dam.2015.04.018
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We consider proper edge colorings of a graph G using colors of the set {1,..., k}. Such a coloring is called neighbor sum distinguishing if for any uv is an element of E(G), the sum of colors of the edges incident to u is different from the sum of the colors of the edges incident to v. The smallest value of k in such a coloring of G is denoted by ndi(Sigma)(G). Let mad(G) and Delta(G) denote the maximum average degree and the maximum degree of a graph G, respectively. In this paper we show that, for a graph G without isolated edges, if mad(G) < 8/3, then ndi(Sigma)(G) <= max{Delta(G) + 1,7}; and if mad(G) < 3, then ndi(Sigma)(G) <= max {Delta(G) + 2,7}. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码:119 / 125
页数:7
相关论文
共 17 条
[1]   r-Strong edge colorings of graphs [J].
Akbari, S. ;
Bidkhori, H. ;
Nosrati, N. .
DISCRETE MATHEMATICS, 2006, 306 (23) :3005-3010
[2]   Adjacent vertex distinguishing edge-colorings [J].
Balister, P. N. ;
Gyori, E. ;
Lehel, J. ;
Schelp, R. H. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (01) :237-250
[3]  
Bonamy M., NEIGHBOUR SUM DISTIN
[4]  
Bu Y., 2011, DISCUSS MATH GRAPH T, V31, P429
[5]  
Dong A., 2012, DISCRETE MATH ALGORI, V4, P125
[6]  
Dong AJ, 2014, DISCRETE APPL MATH, V166, P84, DOI 10.1016/j.dam.2013.10.009
[7]   On the neighbour-distinguishing index of a graph [J].
Edwards, Keith ;
Hornak, Mirko ;
Wozniak, Mariusz .
GRAPHS AND COMBINATORICS, 2006, 22 (03) :341-350
[8]   Neighbor Sum Distinguishing Index [J].
Flandrin, Evelyne ;
Marczyk, Antoni ;
Przybylo, Jakub ;
Sacle, Jean-Francois ;
Wozniak, Mariusz .
GRAPHS AND COMBINATORICS, 2013, 29 (05) :1329-1336
[9]   Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number [J].
Hatami, H .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 95 (02) :246-256
[10]   On Neighbor-Distinguishing Index of Planar Graphs [J].
Hornak, Mirko ;
Huang, Danjun ;
Wang, Weifan .
JOURNAL OF GRAPH THEORY, 2014, 76 (04) :262-278