Geodesic
A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1.

Voir la notice de l'article provenant de la source Episciences

How can one distinguish the adjacent vertices of a graph through an edge-weighting? In the last decades, this question has been attracting increasing attention, which resulted in the active field of distinguishing labellings. One of its most popular problems is the one where neighbours must be distinguishable via their incident sums of weights. An edge-weighting verifying this is said neighbour-sum-distinguishing. The popularity of this notion arises from two reasons. A first one is that designing a neighbour-sum-distinguishing edge-weighting showed up to be equivalent to turning a simple graph into a locally irregular (i.e., without neighbours with the same degree) multigraph by adding parallel edges, which is motivated by the concept of irregularity in graphs. Another source of popularity is probably the influence of the famous 1-2-3 Conjecture, which claims that such weightings with weights in {1,2,3} exist for graphs with no isolated edge. The 1-2-3 Conjecture has recently been investigated from a decompositional angle, via so-called locally irregular decompositions, which are edge-partitions into locally irregular subgraphs. Through several recent studies, it was shown that this concept is quite related to the 1-2-3 Conjecture. However, the full connexion between all those concepts was not clear. In this work, we propose an approach that generalizes all concepts above, involving coloured weights and sums. As a consequence, we get another interpretation of several existing results related to the 1-2-3 Conjecture. We also come up with new related conjectures, to which we give some support. 
@article{DMTCS_2019_21_1_a0,
     author = {Baudon, Olivier and Bensmail, Julien and Davot, Tom and Hocquard, Herv\'e and Przyby{\l}o, Jakub and Senhaji, Mohammed and Sopena, Eric and Wo\'zniak, Mariusz},
     title = {A general decomposition theory for the 1-2-3 {Conjecture} and locally irregular decompositions},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2019},
     doi = {10.23638/DMTCS-21-1-2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-2/}
}
TY  - JOUR
AU  - Baudon, Olivier
AU  - Bensmail, Julien
AU  - Davot, Tom
AU  - Hocquard, Hervé
AU  - Przybyło, Jakub
AU  - Senhaji, Mohammed
AU  - Sopena, Eric
AU  - Woźniak, Mariusz
TI  - A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-2/
DO  - 10.23638/DMTCS-21-1-2
LA  - en
ID  - DMTCS_2019_21_1_a0
ER  - 
%0 Journal Article
%A Baudon, Olivier
%A Bensmail, Julien
%A Davot, Tom
%A Hocquard, Hervé
%A Przybyło, Jakub
%A Senhaji, Mohammed
%A Sopena, Eric
%A Woźniak, Mariusz
%T A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-2/
%R 10.23638/DMTCS-21-1-2
%G en
%F DMTCS_2019_21_1_a0
Baudon, Olivier; Bensmail, Julien; Davot, Tom; Hocquard, Hervé; Przybyło, Jakub; Senhaji, Mohammed; Sopena, Eric; Woźniak, Mariusz. A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi : 10.23638/DMTCS-21-1-2. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-2/

Cité par Sources :