An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index

Abstract

A total k-weighting of a graph G is an assignment of integers from the set {1,..., k} to the vertices and edges of G. We say that is neighbor expanded sum distinguishing, or NESD for short, if σ w2N(v) (f(vw) + f(w)) differs from σ w2N(u) (f(uw) + f(w)) for every two adjacent vertices v and u of G. The neighbor expanded sum distinguishing index of G, denoted by egndi σ (G), is the minimum positive integer k for which there exists an NESD weighting of G. An NESD weighting was introduced and investigated by Flandrin et al. (2017), where they conjectured that egndi σ (G) ≤ 2 for any graph G. They examined some special classes of graphs, while proving that egndiP(G) ≤ x(G) + 1. We improve this bound and show that egndiP(G) ≤ 3 for any graph G. We also show that the conjecture holds for all bipartite, 3-regular and 4-regular graphs.