Authors: Vučković, Bojan 
Title: An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index
Journal: Discussiones Mathematicae - Graph Theory
Issue Date: 1-Jan-2018
Rank: M22
ISSN: 1234-3099
DOI: 10.7151/dmgt.2130
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.
Keywords: general edge coloring | neighbor sum distinguishing index | total coloring
Publisher: Sciendo
Project: Development of new information and communication technologies, based on advanced mathematical methods, with applications in medicine, telecommunications, power systems, protection of national heritage and education 

Show full item record

Page view(s)

checked on Aug 5, 2023

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.