DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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


Authors:

J. Bensmail

Julien Bensmail

Université Côte d'Azur

email: julien.bensmail.phd@gmail.com

0000-0002-9292-394X

F. Fioravantes

Foivos Fioravantes

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

email: foivos.fioravantes@inria.fr

Title:

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

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2022-01-19 , Revised: 2022-09-20 , Accepted: 2022-09-20 , Available online: 2022-10-11 , https://doi.org/10.7151/dmgt.2473

Abstract:

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.

Keywords:

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

References:

  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 $3$s 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

Close