A notion of vertex equitability for proper labellings
- Creators
- Bensmail, Julien
- Others:
- Combinatorics, Optimization and Algorithms for Telecommunications (COATI) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Université côte d'azur
Description
We introduce an equitable version of proper labellings of graphs, where the notion of equitability is with respect to the resulting vertex sums.That is, we are interested in $k$-labellings where, when computing the sums of labels incident to the vertices,we get a vertex-colouring that is not proper only, but also equitable.For a given graph $G$, we are interested in the parameter $\overline{\chi}_\Sigma(G)$, which is the smallest $k \geq 1$ (if any) such that $G$ admits such $k$-labellings.Through examples of particular graph classes, we observe that this new parameter $\overline{\chi}_\Sigma$ behaves sort of similarly to the parameters $\chi_\Sigma$ and $s$,which parameters lie behind the 1-2-3 Conjecture and the irregularity strength of graphs, in a more or less strong way,depending on the graphs considered. We then prove general bounds on $\overline{\chi}_\Sigma$, showing that,in some contexts (trees and connected graphs with large minimum degree), this parameter is bounded above by roughly $\frac{3n}{4}$ for an $n$-graph.We also prove that determining $\overline{\chi}_\Sigma$ is \textsf{NP}-hard in general,and finish off with directions for further work on the topic.
Additional details
- URL
- https://hal.science/hal-04012367
- URN
- urn:oai:HAL:hal-04012367v1
- Origin repository
- UNICA