Geodesic
On proper $2$-labellings distinguishing by sums, multisets or products
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 863-878

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {44},
     number = {3},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/