摘要
Let Ф ： E（G）→ {1, 2,…, k}be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if ∑eЭu Ф（e）≠∑eЭu Ф（e） for each edge uv∈E（G）.The smallest value k for which G has such a coloring is denoted by χ＇Σ（G） which makes sense for graphs containing no isolated edge（we call such graphs normal）. It was conjectured by Flandrin et al. that χ＇Σ（G） ≤△（G） ＋ 2 for all normal graphs,except for C5. Let mad（G） = max{（2｜E（H）｜）/（｜V（H）｜）｜HЭG}be the maximum average degree of G. In this paper,we prove that if G is a normal graph with△（G）≥5 and mad（G） 〈 3-2/（△（G））, then χ＇Σ（G）≤△（G） ＋ 1. This improves the previous results and the bound △（G） ＋ 1 is sharp.
Let Ф ： E（G）→ {1, 2,…, k}be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if ∑eЭu Ф（e）≠∑eЭu Ф（e） for each edge uv∈E（G）.The smallest value k for which G has such a coloring is denoted by χ＇Σ（G） which makes sense for graphs containing no isolated edge（we call such graphs normal）. It was conjectured by Flandrin et al. that χ＇Σ（G） ≤△（G） ＋ 2 for all normal graphs,except for C5. Let mad（G） = max{（2｜E（H）｜）/（｜V（H）｜）｜HЭG}be the maximum average degree of G. In this paper,we prove that if G is a normal graph with△（G）≥5 and mad（G） 〈 3-2/（△（G））, then χ＇Σ（G）≤△（G） ＋ 1. This improves the previous results and the bound △（G） ＋ 1 is sharp.
基金
Supported by the National Natural Science Foundation of China(11471193,11631014)
the Foundation for Distinguished Young Scholars of Shandong Province(JQ201501)
the Fundamental Research Funds of Shandong University
Independent Innovation Foundation of Shandong University(IFYT14012)
