Skip to Main content Skip to Navigation

Going Wide with the 1-2-3 Conjecture

Julien Bensmail 1 Hervé Hocquard 2 Pierre-Marie Marcille 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In the so-called 1-2-3 Conjecture, the question is, for any connected graph not isomorphic to $K_2$, whether we can label its edges with 1,2,3 so that no two adjacent vertices are incident to the same sum of labels. Many aspects of this conjecture have been investigated over the last past years, related both to the conjecture itself and to variations of it. Such variations include different generalisations, such as generalisations to more general graph structures (digraphs, hypergraphs, etc.) and generalisations with stronger distinction requirements. In this work, we introduce a new general problem, which holds essentially as a generalisation of the 1-2-3 Conjecture to a larger range. In this variant, a radius $r\geq2$ is fixed, and the main task, given a graph, is, if possible, to label its edges so that any two vertices at distance at most $r$ are distinguished through their sums of labels assigned to their edges at distance at most $r$. We investigate several general aspects of this problem, in particular the importance of $r$ and its influence on the smallest number of labels needed to label graphs. We also show connections between our general problem and several other notions of graph theory, from both the distinguishing labelling field (e.g. irregularity strength of graphs) and the more general chromatic theory field (e.g. chromatic index of graphs).
Document type :
Complete list of metadata
Contributor : Julien Bensmail <>
Submitted on : Wednesday, May 12, 2021 - 2:18:30 PM
Last modification on : Thursday, May 13, 2021 - 3:40:54 AM


Files produced by the author(s)


  • HAL Id : hal-03225353, version 1


Julien Bensmail, Hervé Hocquard, Pierre-Marie Marcille. Going Wide with the 1-2-3 Conjecture. [Research Report] Université Côte d'Azur; Université de Bordeaux; ENS Lyon. 2021. ⟨hal-03225353⟩



Record views


Files downloads