Skip to Main content Skip to Navigation
Reports

Further Results on an Equitable 1-2-3 Conjecture

Julien Bensmail 1 Foivos Fioravantes 1 Fionn Mc Inerney 2 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this work, we consider equitable proper labellings of graphs, which were recently introduced by Baudon, Pilśniak, Przybyƚo, Senhaji, Sopena, and Wozńiak. Given a graph G, the goal is to assign labels to the edges so that 1) no two adjacent vertices are incident to the same sum of labels, and 2) every two labels are assigned about the same number of times. Particularly , we aim at designing such equitable proper k-labellings of G with k being as small as possible. In connection with the so-called 1-2-3 Conjecture, it might be that labels 1,2,3 are, a few obvious exceptions apart, always sufficient to achieve this just as in the non-equitable version of the problem. We provide results regarding some open questions about equitable proper labellings. Via a hardness result, we first prove that there exist infinitely many graphs for which more labels are required in the equitable version than in the non-equitable version. This remains true in the bipartite case. We finally show that, for every $k≥3$, every k-regular bipartite graph admits an equitable proper k-labelling.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02533537
Contributor : Julien Bensmail <>
Submitted on : Monday, April 6, 2020 - 2:54:53 PM
Last modification on : Tuesday, May 26, 2020 - 6:50:53 PM

File

equitable123.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02533537, version 1

Citation

Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, Nicolas Nisse. Further Results on an Equitable 1-2-3 Conjecture. [Research Report] Université Côte d'Azur, CNRS, I3S, France; Inria Sophia Antipolis; Aix-Marseille Université (AMU). 2020. ⟨hal-02533537⟩

Share

Metrics

Record views

68

Files downloads

33