Back to Search Start Over

A note on a directed version of the 1-2-3 Conjecture.

Authors :
Horňák, Mirko
Przybyło, Jakub
Woźniak, Mariusz
Source :
Discrete Applied Mathematics. Feb2018, Vol. 236, p472-476. 5p.
Publication Year :
2018

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0166218X
Volume :
236
Database :
Academic Search Index
Journal :
Discrete Applied Mathematics
Publication Type :
Academic Journal
Accession number :
126943940
Full Text :
https://doi.org/10.1016/j.dam.2017.11.016