Neighbour sum distinguishing edge-weightings with local constraints
This work advances graph theory by establishing new sufficient conditions for neighbour sum distinguishing edge-weightings with local constraints, addressing open problems for graphs with bounded maximum degree.
The paper proves that every nice graph (no component isomorphic to K2) with maximum degree at most 5 admits a neighbour sum distinguishing (Δ(G)+2)-edge-weighting with local constraints, and that every nice graph admits a neighbour sum distinguishing 7-edge-weighting with local constraints. Nice bipartite graphs admit a neighbour sum distinguishing 6-edge-weighting with local constraints.
A $k$-edge-weighting of $G$ is a mapping $ω:E(G)\longrightarrow \{1,\ldots,k\}$. The edge-weighting of $G$ naturally induces a vertex-colouring $σ_ω:V(G)\longrightarrow \mathbb{N}$ given by$σ_ω(v)=\sum_{u\in N_G(v)}ω(vu)$ for every $v\in V(G)$. The edge-weighting $ω$ is neighbour sum distinguishing if it yields a proper vertex-colouring $σ_ω$, \emph{i.e.}, $σ_ω(u)\neq σ_ω(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. A 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 $(Δ(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.