ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in press


J. Bensmail

Julien Bensmail

Université Côte d'Azur



F. Fioravantes

Foivos Fioravantes

Université Côte d'Azur, CNRS, Inria, I3S



On proper $2$-labellings distinguishing by sums, multisets or products



Discussiones Mathematicae Graph Theory

Received: 2022-01-19 , Revised: 2022-09-20 , Accepted: 2022-09-20 , Available online: 2022-10-11 ,


Given a graph $G$, a $k$-labelling $\ell$ of $G$ is an assignment $\ell: E(G) \rightarrow \{1,\dots,k\}$ of labels from $\{1,\dots,k\}$ to the edges. We say that $\ell$ 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.


proper labelling, sum of labels, multiset of labels, product of labels


  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.
  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.
  3. J. Bensmail, F. Fioravantes and F. Mc Inerney, On the role of $3$s for the $1$-$2$-$3$ Conjecture, Theoret. Comput. Sci. 892 (2021) 238–257.
  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.
  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.
  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.
  7. R.L. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37(2) (1941) 194–197.
  8. G.J. Chang, C. Lu, J. Wu and Q. Yu, Vertex-coloring edge-weightings of graphs, Taiwanese J. Math. 15 (2011) 1807–1813.
  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.
  11. A. Dudek and D. Wajc, On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci. 13(3) (2011) 45–50.
  12. J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2021) #DS6.
  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.
  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.
  15. M. Karoński, T. Łuczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004) 151–157.
  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.
  18. N. Paramaguru and R. Sampathkumar, Graphs with vertex-coloring and detectable $2$-edge-weighting, AKCE Int. J. Graphs Comb. 13 (2016) 146–156.
  19. B. Seamone, The $1$-$2$-$3$ Conjecture and related problems: a survey (2012).
  20. J. Skowronek-Kaziów, Multiplicative vertex-colouring weightings of graphs, Inform. Process. Lett. 112(5) (2012) 191–194.
  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.
  22. B. Vučković, Multi-set neighbor distinguishing $3$-edge coloring, Discrete Math. 341 (2018) 820–824.