MathDBThe 1–2–3 Conjecture for neighbour-sum-distinguishing edge weightings
The 1–2–3 Conjecture for neighbour-sum-distinguishing edge weightings
Let be a connected graph with at least three vertices. An edge weighting assigns a weight from to every edge of , and the sum at a vertex is the sum of the weights on its incident edges. 1–2–3 Conjecture. Every such graph has an edge weighting for which adjacent vertices receive distinct sums of their incident weights. This conjecture asks whether three edge weights always suffice to distinguish the incident-weight sums of adjacent vertices; it remains open in general, although the paper proves the Standard -Conjecture for graphs with sufficiently large minimum degree.
Equivalent formulations 1
Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.
The 1–2–3 Conjecture for neighbour sum-distinguishing edge-weightings
A graph has no isolated edges if none of its connected components is a single edge. A weighting is sum-distinguishing if the weighted degrees
are distinct for the endpoints of every edge, where is the set of edges incident with . 1–2–3 Conjecture. For every graph without isolated edges, there exists a weighting that sum-distinguishes all neighbours in . This is a fundamental open problem on graph edge-weightings; the claim is open in general.
source: Julien Bensmail and Jakub Przybyło, “Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture”, arXiv:1803.07409 (2018).
Sources & referencesView supporting material
Primary source
Jakub Przybyło, “On the Standard (2,2)-Conjecture”, arXiv:1911.00867 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.