Article ID Journal Published Year Pages File Type
4949785 Discrete Applied Mathematics 2017 9 Pages PDF
Abstract
In this paper, we consider the following question, which stands as a directed analogue of the well-known 1-2-3 Conjecture: Given any digraph D with no arc uv⃗ verifying d+(u)=d−(v)=1, is it possible to weight the arcs of D with weights among {1,2,3} so that, for every arc uv⃗ of D, the sum of incident weights out-going from u is different from the sum of incident weights in-coming to v? We answer positively to this question, and investigate digraphs for which even the weights among {1,2} are sufficient. In relation with the so-called 1-2 Conjecture, we also consider a total version of the problem, which we prove to be false. Our investigations turn to have interesting relations with open questions related to the 1-2-3 Conjecture.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,