Going Wide with the 1-2-3 Conjecture - Université Côte d'Azur Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2021

Going Wide with the 1-2-3 Conjecture

Résumé

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).
Fichier principal
Vignette du fichier
radius123.pdf (501.06 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03225353 , version 1 (12-05-2021)
hal-03225353 , version 2 (29-05-2022)

Identifiants

  • HAL Id : hal-03225353 , version 1

Citer

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-03225353v1⟩

Collections

LARA
280 Consultations
132 Téléchargements

Partager

Gmail Facebook X LinkedIn More