Geodesic
On proper $2$-labellings distinguishing by sums, multisets or products
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 863-878 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Given a graph G, a k-labelling 𝓁 of G is an assignment 𝓁: E(G) →{1,…,k} of labels from {1,…,k} to the edges. We say that 𝓁 is s-proper, m-proper or p-proper, if no two adjacent vertices of G are incident to the same sum, multiset or product, respectively, of labels. Proper labellings are part of the field of distinguishing labellings, and have been receiving quite some attention over the last decades, in particular in the context of the well-known 1-2-3 Conjecture. In recent years, quite some progress was made towards the main questions of the field, with, notably, the analogues of the 1-2-3 Conjecture for m-proper and p-proper labellings being solved. This followed mainly from a better global understanding of these types of labellings. In this note, we focus on a question raised by Paramaguru and Sampathkumar, who asked whether graphs with m-proper 2-labellings always admit s-proper 2-labellings. A negative answer to this question was recently given by Luiz, who provided infinite families of counterexamples. We give a more general result, showing that recognising graphs with m-proper 2 -labellings but no s-proper 2-labellings is an NP-hard problem. We also prove a similar result for m-proper 2-labellings and p-proper 2-labellings, and raise a few directions for further work on the topic.
Keywords: proper labelling, sum of labels, multiset of labels, product of labels 
@article{DMGT_2024_44_3_a2,
     author = {Bensmail, Julien and Fioravantes, Foivos},
     title = {On proper $2$-labellings distinguishing by sums, multisets or products},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {863--878},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a2/}
}
TY  - JOUR
AU  - Bensmail, Julien
AU  - Fioravantes, Foivos
TI  - On proper $2$-labellings distinguishing by sums, multisets or products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 863
EP  - 878
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a2/
LA  - en
ID  - DMGT_2024_44_3_a2
ER  - 
%0 Journal Article
%A Bensmail, Julien
%A Fioravantes, Foivos
%T On proper $2$-labellings distinguishing by sums, multisets or products
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 863-878
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a2/
%G en
%F DMGT_2024_44_3_a2
Bensmail, Julien; Fioravantes, Foivos. On proper $2$-labellings distinguishing by sums, multisets or products. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 863-878. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a2/

[1] L. Addario-Berry, R.E.L. Aldred, K. Dalal and B.A. Reed, Vertex colouring edge partitions, J. Combin. Theory Ser. B 94 (2005) 237–244. https://doi.org/10.1016/j.jctb.2005.01.001

[2] O. Baudon, J. Bensmail, J. Przybyło and M. Woźniak, On decomposing regular graphs into locally irregular subgraphs, European J. Combin. 49 (2015) 90–104. https://doi.org/10.1016/j.ejc.2015.02.031

[3] J. Bensmail, F. Fioravantes and F. Mc Inerney, On the role of 3s for the 1-2-3 Conjecture, Theoret. Comput. Sci. 892 (2021) 238–257. https://doi.org/10.1016/j.tcs.2021.09.023

[4] J. Bensmail, F. Fioravantes, F. Mc Inerney and N. Nisse, Further results on an equitable 1-2-3 Conjecture, Discrete Appl. Math. 297 (2021) 1–20. https://doi.org/10.1016/j.dam.2021.02.037

[5] J. Bensmail, H. Hocquard, D. Lajou and É. Sopena, Further evidence towards the multiplicative 1-2-3 Conjecture, Discrete Appl. Math. 307 (2022) 135–144. https://doi.org/10.1016/j.dam.2021.10.014

[6] J. Bensmail, H. Hocquard, D. Lajou and É. Sopena, A proof of the multiplicative 1 -2-3 Conjecture, in: Algorithms and Discrete Applied Mathematics, N. Balachandran and R.Inkulu (Ed(s)), (Lecture Notes in Comput. Sci. 13179 2022) 3–14. https://doi.org/10.1007/978-3-030-95018-7_1

[7] R.L. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37(2) (1941) 194–197. https://doi.org/10.1017/S030500410002168X

[8] G.J. Chang, C. Lu, J. Wu and Q. Yu, Vertex-coloring edge-weightings of graphs, Taiwanese J. Math. 15 (2011) 1807–1813. https://doi.org/10.11650/twjm/1500406380

[9] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197–210.

[10] A. Dehghan, A. Ahadi and M.-R. Sadeghi, Algorithmic complexity of proper labeling problems, Theoret. Comput. Sci. 495 (2013) 25–36. https://doi.org/10.1016/j.tcs.2013.05.027

[11] A. Dudek and D. Wajc, On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci. 13(3) (2011) 45–50. https://doi.org/10.46298/dmtcs.548

[12] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2021) #DS6. https://doi.org/10.37236/27

[13] F. Havet, N. Paramaguru and R. Sampathkumar, Detection number of bipartite graphs and cubic graphs, Discrete Math. Theor. Comput. Sci. 16(3) (2014) 333–342. https://doi.org/10.46298/dmtcs.642

[14] 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. https://doi.org/10.1016/j.jctb.2009.06.002

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

[16] A.G. Luiz, Graceful Labellings and Neighbour-Distinguishing Labellings of Graphs (Ph.D. Thesis, University of Campinas, 2018).

[17] K. Szabo Lyngsie, On neighbour sum-distinguishing {0,1}-edge-weightings of bipartite graphs, Discrete Math. Theor. Comput. Sci. 20(1) (2018) 21. https://doi.org/10.23638/DMTCS-20-1-21

[18] N. Paramaguru and R. Sampathkumar, Graphs with vertex-coloring and detectable 2-edge-weighting, AKCE Int. J. Graphs Comb. 13 (2016) 146–156. https://doi.org/10.1016/j.akcej.2016.06.008

[19] B. Seamone, The 1-2-3 Conjecture and related problems: a survey (2012). http://arxiv.org/abs/1211.5122

[20] J. Skowronek-Kaziów, Multiplicative vertex-colouring weightings of graphs, Inform. Process. Lett. 112(5) (2012) 191–194. https://doi.org/10.1016/j.ipl.2011.11.009

[21] C. Thomassen, Y. Wu and C.-Q. Zhang, The 3-flow conjecture, factors modulo k, and the 1-2-3-Conjecture, J. Combin. Theory Ser. B 121 (2016) 308–325. https://doi.org/10.1016/j.jctb.2016.06.010

[22] B. Vučković, Multi-set neighbor distinguishing 3-edge coloring, Discrete Math. 341 (2018) 820–824. https://doi.org/10.1016/j.disc.2017.12.001