Neighbour sum distinguishing edge-weightings with local constraints

Antoine Dailly (UNAM; El{\AA}1/4bieta Sidorowicz; G-SCOP\_OC; LIMOS)

arxiv: 2203.11521 · v2 · submitted 2022-03-22 · 💻 cs.DM · math.CO

Neighbour sum distinguishing edge-weightings with local constraints

Antoine Dailly (UNAM , G-SCOP\_OC , LIMOS) , El{\AA}1/4bieta Sidorowicz This is my paper

Pith reviewed 2026-05-24 11:33 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords neighbour sum distinguishingedge-weightinglocal constraintsnice graphsmaximum degreebipartite graphsgraph colouring

0 comments

The pith

Every nice graph with maximum degree at most 5 admits a neighbour sum distinguishing (Δ+2)-edge-weighting where vertices of degree at least 2 have at least two different incident weights.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves existence results for edge-weightings that make the sums of weights at adjacent vertices all different while adding a local requirement that certain vertices see at least two distinct weights among their incident edges. For any nice graph (one with no isolated K2 component) whose largest degree is five or less, the number of distinct weights needed is at most Δ+2 and the local requirement applies to every vertex of degree two or more. Separate arguments show that seven weights suffice for the local requirement at vertices of degree six and higher in arbitrary nice graphs, and that six weights suffice with the local requirement at all degree-two-or-higher vertices when the graph is bipartite.

Core claim

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.

What carries the argument

A neighbour sum distinguishing k-edge-weighting (an assignment of integers from 1 to k to edges so that adjacent vertices receive different sums) equipped with the additional local constraint that every vertex of sufficient degree is incident to at least two edges carrying different weights.

If this is right

All nice graphs of maximum degree 5 possess such a weighting using at most Δ+2 weights with the local condition enforced everywhere.
All nice graphs possess a 7-weighting satisfying the neighbour-sum condition and the local condition at every vertex of degree 6 or more.
Nice bipartite graphs possess a 6-weighting satisfying the neighbour-sum condition and the local condition at every vertex of degree 2 or more.
The local non-monochromatic requirement can be met simultaneously with the global sum-distinguishing property under the stated degree and bipartiteness hypotheses.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same local constraint may require more weights than the classical neighbour-sum-distinguishing problem without the constraint.
The inductive techniques used here could be tested for applicability to total weightings or other sum-distinguishing labelings that incorporate similar local diversity rules.
For graphs with maximum degree larger than 5 the gap between the 7-weight bound and the unconstrained problem remains open.

Load-bearing premise

Standard inductive or greedy constructions on finite simple graphs suffice to produce the required weightings without global obstructions created by the local diversity condition.

What would settle it

A single nice graph of maximum degree 5 for which no assignment of the numbers 1 through 7 to its edges produces distinct vertex sums at adjacent vertices while also ensuring every degree-at-least-2 vertex sees at least two different weights on its incident edges.

read the original abstract

A $k$-edge-weighting of $G$ is a mapping $\omega:E(G)\longrightarrow \{1,\ldots,k\}$. The edge-weighting of $G$ 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. 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 $(\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This adds local non-monochromatic constraints to neighbour-sum distinguishing weightings and proves three explicit bounds for nice graphs.

read the letter

This paper takes the neighbour sum distinguishing edge weighting problem and adds a local constraint that incident edges at higher degree vertices must use at least two different weights. It then proves three existence results with specific upper bounds on the number of weights needed. The first result covers nice graphs with maximum degree 5, showing they admit such a weighting using at most Δ+2 weights, with the local condition holding at all vertices of degree 2 or more. The second shows that any nice graph has a 7-weighting where the local condition applies only to vertices of degree 6 and above. The third is for nice bipartite graphs, where 6 weights suffice with the condition at degree 2 and up. These bounds and the exact placement of the local constraint represent the new contributions, as the local non-monochromatic requirement does not appear in the standard references for this area. The paper is built on existence proofs for finite simple graphs that are nice, meaning no isolated K2 components. This setup avoids some trivial counterexamples and is a common move in the field. The arguments are likely inductive or greedy constructions based on the number of vertices or edges, which is appropriate here and does not introduce any self-referential or fitted parameters. One soft spot is that the general bound of 7 is somewhat higher than the classic 3 from the 1-2-3 conjecture, but the added constraint explains the increase. Another is that the proofs are not visible in the abstract, so it is possible they involve many cases, though nothing indicates a load-bearing flaw. The results do not claim optimality, which keeps expectations realistic. Readers working on graph labeling, distinguishing sums, and related conjectures would get the most from this. It is a targeted advance inside discrete mathematics rather than something that changes methods outside the subfield. The work is coherent on its own terms and engages the literature directly. I recommend sending it for peer review. The theorems are stated clearly enough and the novelty in the constraints is real, so referees can usefully check the constructions.

Referee Report

0 major / 3 minor

Summary. The paper proves three existence theorems for neighbour-sum-distinguishing k-edge-weightings of nice graphs (finite simple graphs with no K2 components) that additionally satisfy a local constraint: every vertex of sufficiently high degree is incident to at least two edges of distinct weights. Theorem 1 asserts that every nice graph with Δ(G) ≤ 5 admits such a weighting with k = Δ(G) + 2 where the local constraint holds for all vertices of degree ≥ 2. Theorem 2 asserts that every nice graph admits such a weighting with k = 7 where the local constraint holds for all vertices of degree ≥ 6. Theorem 3 asserts that every nice bipartite graph admits such a weighting with k = 6 where the local constraint holds for all vertices of degree ≥ 2. The weightings induce proper vertex colourings via the sum of incident weights.

Significance. If the proofs are correct, the results extend the literature on neighbour-sum-distinguishing edge weightings (related to the 1-2-3 conjecture) by adding explicit local non-monochromaticity constraints at high-degree vertices. The obtained bounds (Δ+2 for Δ≤5, constant 7 in general, constant 6 for bipartite graphs) are close to the best known bounds without the local constraints and are obtained via standard inductive or greedy combinatorial arguments on finite graphs. The paper supplies explicit, falsifiable existence statements for a well-defined class of graphs and constraints.

minor comments (3)

The abstract and introduction should explicitly state the precise definition of 'nice' (no K2 components) and the local constraint (at least two distinct weights at each qualifying vertex) in a single sentence for quick reference.
Notation for the induced sum colouring σ_ω is introduced in the abstract but should be restated with the domain and codomain when first used in Section 1.
The paper should include a short table or paragraph comparing the new bounds with the best known bounds for the unconstrained neighbour-sum-distinguishing problem (e.g., the 1-2-3 conjecture results).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of our results and for recommending minor revision. No major comments appear in the report, so we have no points requiring point-by-point response.

Circularity Check

0 steps flagged

No circularity in combinatorial existence proofs

full rationale

The paper consists of three existence theorems for neighbour-sum-distinguishing edge weightings on finite nice graphs, proved via standard inductive or greedy combinatorial constructions. No quantities are defined in terms of other quantities by construction, no parameters are fitted to data and then relabeled as predictions, and no load-bearing steps reduce to self-citations or ansatzes imported from prior author work. The derivation chain is self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard axioms of finite simple graph theory (undirected edges, no loops or multiple edges) and the definition of nice graphs. No free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)

domain assumption Graphs are finite, undirected, simple, and have no components isomorphic to K2 (the 'nice' condition).
Explicitly stated in the abstract as the class of graphs under consideration.
domain assumption Standard combinatorial existence arguments (induction or greedy assignment) suffice to construct the required weightings.
Implicit in any proof of such labeling theorems; the abstract provides no counterexample or obstruction.

pith-pipeline@v0.9.0 · 5842 in / 1604 out tokens · 31023 ms · 2026-05-24T11:33:21.892063+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

[1]

Alon, Combinatorial Nullstellensatz , Combin

N. Alon, Combinatorial Nullstellensatz , Combin. Probab. Comput. 8 (1999), 7–29

work page 1999
[2]

Bensmail, A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graph s, Discrete Appl

J. Bensmail, A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graph s, Discrete Appl. Math. 257 (2019) 31–39

work page 2019
[3]

Dailly, ´E

A. Dailly, ´E. Duchˆ ene, A. Parreau, E. Sidorowicz, The neighbour sum distinguishing relaxed edge colouring , Applied Mathematics and Computation 419 (2022) 126864

work page 2022
[4]

Dudek, D

A. Dudek, D. Wajc, On the complexity of vertex-coloring edge-weightings , Discrete Math. Theoret. Comput. Sci. 13 (3) (2011) 45–50

work page 2011
[5]

Flandrin, A

E. Flandrin, A. Marczyk, J. Przyby/suppress lo, J-F. Sacle, M. Wo´ zniak,Neighbour sum distin- guishing index , Graphs Combin. 29(5) (2013) 1329–1336

work page 2013
[6]

Y. Gao, G. Wang, J. Wu, A relaxed case on 1-2-3 conjecture , Graphs Combin. 32 (4) (2016) 1415–1421

work page 2016
[7]

J. Huo, Y. Wang, W. Wang, Neighbour-sum-distinguishing edge choosability of subcu bic graphs, J. Comb. Optim. 34 (3) (2017) 742–759

work page 2017
[8]

Kalkowski, M

M. Kalkowski, M. Karo´ nski, F. Pfender, A new upper bound for the irregularity strength of graphs , SIAM J. Discrete Math. 25(3) (2011) 1319–1321

work page 2011
[9]

Karo´ nski, T

M. Karo´ nski, T. /suppress Luczak, A. Thomason,Edge weights and vertex colours , J. Combin. Theory Ser. B 91 (2004) 151–157

work page 2004
[10]

H. Lu, Q. Yu, C.-Q. Zhang, Vertex-colouring 2-edge-weighting of graphs , European J. Combin. 32 (2011) 21–27

work page 2011
[11]

Przyby/suppress lo,Neighbor distinguishing edge colorings via the combinator ial nullstellensatz , SIAM J

J. Przyby/suppress lo,Neighbor distinguishing edge colorings via the combinator ial nullstellensatz , SIAM J. Discrete Math. 27 (3) (2013) 1313–1322

work page 2013
[12]

Przyby/suppress lo,A note on asymptotically optimal neighbour sum distinguish ing colourings, European Journal of Combinatorics 77 (2019) 49–56

J. Przyby/suppress lo,A note on asymptotically optimal neighbour sum distinguish ing colourings, European Journal of Combinatorics 77 (2019) 49–56

work page 2019
[13]

Przyby/suppress lo,The 1-2-3 Conjecture almost holds for regular graphs , J

J. Przyby/suppress lo,The 1-2-3 Conjecture almost holds for regular graphs , J. Combinatorial Theory, Ser. B 147 (2020) 183–200

work page 2020
[14]

Przyby/suppress lo, T-L

J. Przyby/suppress lo, T-L. Wong,Neighbour distinguishing edge colourings via the Combinat orial Nullstellensatz revisited , J. Graph Theory 80 (2015) 299–312

work page 2015
[15]

Thomassen, Y

C. Thomassen, Y. Wu, C.-Q. Zhang, The 3-ﬂow conjecture, factors modulo k, and the 1-2-3-conjecture J. Combin. Theory, Ser. B, 121 (2016) 308–325

work page 2016
[16]

G. Wang, G. Yan, An improved upper bound for the neighbour sum distinguishin g index of graphs , Discrete Appl. Math. 175 (2014) 126–128

work page 2014
[17]

The 1-2-3 Conjecture and related problems: a survey

B. Seamone, The 1-2-3 Conjecture and related problems: a survey , Technical report, available on-line at http://arxiv.org/abs/1211.5122, 2012. 27

work page internal anchor Pith review Pith/arXiv arXiv 2012

[1] [1]

Alon, Combinatorial Nullstellensatz , Combin

N. Alon, Combinatorial Nullstellensatz , Combin. Probab. Comput. 8 (1999), 7–29

work page 1999

[2] [2]

Bensmail, A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graph s, Discrete Appl

J. Bensmail, A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graph s, Discrete Appl. Math. 257 (2019) 31–39

work page 2019

[3] [3]

Dailly, ´E

A. Dailly, ´E. Duchˆ ene, A. Parreau, E. Sidorowicz, The neighbour sum distinguishing relaxed edge colouring , Applied Mathematics and Computation 419 (2022) 126864

work page 2022

[4] [4]

Dudek, D

A. Dudek, D. Wajc, On the complexity of vertex-coloring edge-weightings , Discrete Math. Theoret. Comput. Sci. 13 (3) (2011) 45–50

work page 2011

[5] [5]

Flandrin, A

E. Flandrin, A. Marczyk, J. Przyby/suppress lo, J-F. Sacle, M. Wo´ zniak,Neighbour sum distin- guishing index , Graphs Combin. 29(5) (2013) 1329–1336

work page 2013

[6] [6]

Y. Gao, G. Wang, J. Wu, A relaxed case on 1-2-3 conjecture , Graphs Combin. 32 (4) (2016) 1415–1421

work page 2016

[7] [7]

J. Huo, Y. Wang, W. Wang, Neighbour-sum-distinguishing edge choosability of subcu bic graphs, J. Comb. Optim. 34 (3) (2017) 742–759

work page 2017

[8] [8]

Kalkowski, M

M. Kalkowski, M. Karo´ nski, F. Pfender, A new upper bound for the irregularity strength of graphs , SIAM J. Discrete Math. 25(3) (2011) 1319–1321

work page 2011

[9] [9]

Karo´ nski, T

M. Karo´ nski, T. /suppress Luczak, A. Thomason,Edge weights and vertex colours , J. Combin. Theory Ser. B 91 (2004) 151–157

work page 2004

[10] [10]

H. Lu, Q. Yu, C.-Q. Zhang, Vertex-colouring 2-edge-weighting of graphs , European J. Combin. 32 (2011) 21–27

work page 2011

[11] [11]

Przyby/suppress lo,Neighbor distinguishing edge colorings via the combinator ial nullstellensatz , SIAM J

J. Przyby/suppress lo,Neighbor distinguishing edge colorings via the combinator ial nullstellensatz , SIAM J. Discrete Math. 27 (3) (2013) 1313–1322

work page 2013

[12] [12]

Przyby/suppress lo,A note on asymptotically optimal neighbour sum distinguish ing colourings, European Journal of Combinatorics 77 (2019) 49–56

J. Przyby/suppress lo,A note on asymptotically optimal neighbour sum distinguish ing colourings, European Journal of Combinatorics 77 (2019) 49–56

work page 2019

[13] [13]

Przyby/suppress lo,The 1-2-3 Conjecture almost holds for regular graphs , J

J. Przyby/suppress lo,The 1-2-3 Conjecture almost holds for regular graphs , J. Combinatorial Theory, Ser. B 147 (2020) 183–200

work page 2020

[14] [14]

Przyby/suppress lo, T-L

J. Przyby/suppress lo, T-L. Wong,Neighbour distinguishing edge colourings via the Combinat orial Nullstellensatz revisited , J. Graph Theory 80 (2015) 299–312

work page 2015

[15] [15]

Thomassen, Y

C. Thomassen, Y. Wu, C.-Q. Zhang, The 3-ﬂow conjecture, factors modulo k, and the 1-2-3-conjecture J. Combin. Theory, Ser. B, 121 (2016) 308–325

work page 2016

[16] [16]

G. Wang, G. Yan, An improved upper bound for the neighbour sum distinguishin g index of graphs , Discrete Appl. Math. 175 (2014) 126–128

work page 2014

[17] [17]

The 1-2-3 Conjecture and related problems: a survey

B. Seamone, The 1-2-3 Conjecture and related problems: a survey , Technical report, available on-line at http://arxiv.org/abs/1211.5122, 2012. 27

work page internal anchor Pith review Pith/arXiv arXiv 2012