Authors: B. Vuèkoviĉ Title: An improved upper bound on neighbor expanded sum distinguishing index Source: Discussiones Mathematicae Graph Theory Received 16.02.2017, Revised 19.03.2018, Accepted 19.03.2018, doi: 10.7151/dmgt.2130 | |
Abstract: A total k-weighting f of a graph G is an assignment of integers from the set {1,...,k} to the vertices and edges of G. We say that f is neighbor expanded sum distinguishing, or NESD for short, if ∑_{w∈N(v)}(f(vw)+f(w)) differs from ∑_{w∈N(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 \nesd(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 \nesd(G)\le 2 for any graph G. They examined some special classes of graphs, while proving that \nesd(G)\le χ(G)+1. We improve this bound and show that \nesd(G)\le 3 for any graph G. We also show that the conjecture holds for all bipartite, 3-regular and 4-regular graphs. | |
Keywords: general edge coloring, total coloring, neighbor sum distinguishing index | |
Links: |