Article in volume
Authors:
Title:
On proper $2$-labellings distinguishing by sums, multisets or products
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 863-878
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:
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197–210.
- 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 - 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 - J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2021) #DS6.
https://doi.org/10.37236/27 - 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 - 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 - 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 - A.G. Luiz, Graceful Labellings and Neighbour-Distinguishing Labellings of Graphs (Ph.D. Thesis, University of Campinas, 2018).
- 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 - 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 - B. Seamone, The $1$-$2$-$3$ Conjecture and related problems: a survey (2012).
http://arxiv.org/abs/1211.5122 - 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 - 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 - 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