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
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/
@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},
year = {2020},
volume = {40},
number = {1},
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
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
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a21/
%G en
%F 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
