Some bounds on the neighbor-distinguishing index of graphs

Let G be a graph with maximum degree Δ and without isolated edges. In this paper, we prove that χa′(G)≤2Δ if 4≤Δ≤5, and χa′(G)≤2.5Δ if Δ≥6. This improves a result in Zhang et al. (2014), which states that χa′(G)≤2.5Δ+5 for any graph G without isolated edges. Moreover, we prove that if G is a semi-regular graph (i.e., each edge of G is incident to at least one Δ-vertex), then χa′(G)≤53Δ+133.