Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

The neighbour sum distinguishing edge-weighting with local constraints

Antoine Dailly 1, 2 Elżbieta Sidorowicz 3 
2 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : A $k$-edge-weighting of $G$ is a mapping $\omega:E(G)\longrightarrow \{1,\ldots,k\}$. The edge-weighting naturally induces a vertex colouring $\sigma_{\omega}:V(G)\longrightarrow \mathbb{N}$ given by $\sigma_{\omega}(v)=\sum_{u\in N_G(v)}\omega(vu)$ for every $v\in V(G)$. The edge-weighting $\omega$ is neighbour sum distinguishing if it yields a proper vertex colouring $\sigma_{\omega}$, \emph{i.e.}, $\sigma_{\omega}(u)\neq \sigma_{\omega}(v)$ for every edge $uv$ of $G$. We investigate a neighbour sum distinguishing edge-weighting with local constraints, namely, we assume that the set of edges incident to a vertex of large degree is not monochromatic. The graph is nice if it has no components isomorphic to $K_2$. We prove that every nice graph with maximum degree at most~5 admits a neighbour sum distinguishing $(\Delta(G)+2)$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights. Furthermore, we prove that every nice graph admits a neighbour sum distinguishing $7$-edge-weighting such that all the vertices of degree at least~6 are incident with at least two edges of different weights. Finally, we show that nice bipartite graphs admit a neighbour sum distinguishing $6$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03615738
Contributor : Antoine Dailly Connect in order to contact the contributor
Submitted on : Monday, March 21, 2022 - 5:54:08 PM
Last modification on : Monday, August 8, 2022 - 5:38:05 PM

Files

edge-weighting_v6.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03615738, version 1
  • ARXIV : 2203.11521

Collections

Citation

Antoine Dailly, Elżbieta Sidorowicz. The neighbour sum distinguishing edge-weighting with local constraints. 2022. ⟨hal-03615738⟩

Share

Metrics

Record views

30

Files downloads

1