Geodesic
An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 323-329.

Voir la notice de l'article provenant de la source Library of Science

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 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 egndiΣ(G) ≤ χ(G) + 1. We improve this bound and show that egndiΣ(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, total coloring, neighbor sum distinguishing index 
@article{DMGT_2020_40_1_a21,
     author = {Vu\v{c}kovi\'c, Bojan},
     title = {An {Improved} {Upper} {Bound} on {Neighbor} {Expanded} {Sum} {Distinguishing} {Index}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {323--329},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a21/}
}
TY  - JOUR
AU  - Vučković, Bojan
TI  - An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 323
EP  - 329
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a21/
LA  - en
ID  - DMGT_2020_40_1_a21
ER  - 
%0 Journal Article
%A Vučković, Bojan
%T An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 323-329
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a21/
%G en
%F DMGT_2020_40_1_a21
Vučković, Bojan. An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 323-329. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a21/

[1] G. Chartrand and P. Zhang, Chromatic Graph Theory (Boca Raton: Chapman & Hall/CRC, 2009).

[2] E. Flandrin, H. Li, A. Marczyk, J.-F. Sacle and M. Woźniak, A note on neighbor expanded sum distinguishing index, Discuss. Math. Graph Theory 37 (2017) 29–37. doi:10.7151/dmgt.1909

[3] M. Karoński, T. Luczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004) 151–157. doi:10.1016/j.jctb.2003.12.001

[4] M. Kalkowski, M. Karoński and F. Pfender, Vertex-coloring edge-weightings: Towards the 1-2-3- conjecture, J. Combin. Theory Ser. B 100 (2010) 347–349. doi:10.1016/j.jctb.2009.06.002

[5] R.L. Brooks, On coloring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194–197. doi:10.1017/S030500410002168X