Article ID Journal Published Year Pages File Type
6871626 Discrete Applied Mathematics 2018 5 Pages PDF
Abstract
The least k such that a given digraph D=(V,A) can be arc-labeled with integers in the interval [1,k] so that the sum of values in-coming to x is distinct from the sum of values out-going from y for every arc (x,y)∈A, is denoted by χ̄Łe(D). This corresponds to one of possible directed versions of the well-known 1-2-3 Conjecture. Unlike in the case of other possibilities, we show that χ̄Łe(D) is unbounded in the family of digraphs for which this parameter is well defined. However, if the family is restricted by excluding the digraphs with so-called lonely arcs, we prove that χ̄Łe(D)≤4, and we conjecture that χ̄Łe(D)≤3 should hold.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,