2022/03/22 by Antoine Dailly, Dailly, Antoine, Sidorowicz, ElÅ1/4bieta · 1 citation
Computer Science · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Security in Wireless Sensor Networks
paper · pdf · doi:10.48550/arxiv.2203.11521
openalex publication_date 2022/03/22 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28
A k-edge-weighting of G is a mapping ω:E(G)\longrightarrow \1,…,k\. The edge-weighting of G naturally induces a vertex-colouring σω:V(G)\longrightarrow ℕ given byσω(v)=∑u∈ NG(v)ω(vu) for every v∈ V(G). The edge-weighting ω is neighbour sum distinguishing if it yields a proper vertex-colouring σω, i.e., σω(u)≠ σω(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 K2. 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.