On a directed variation of the 1-2-3 and 1-2 Conjectures

详细信息    查看全文

• 作者：Emma Barme^a ; Julien Bensmail^b ; ^{julien.bensmail.phd@gmail.com} ; Jakub Przybyło^c ; Mariusz Woźniak^c
• 关键词：1-2-3 Conjecture ; 1-2 Conjecture ; Digraphs
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：123-131
• 全文大小：419 K
• 卷排序：217

文摘

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 DD with no arc uv⃗ verifying d+(u)=d−(v)=1d+(u)=d−(v)=1, is it possible to weight the arcs of DD with weights among {1,2,3}{1,2,3} so that, for every arc uv⃗ of DD, the sum of incident weights out-going from uu is different from the sum of incident weights in-coming to vv? We answer positively to this question, and investigate digraphs for which even the weights among {1,2}{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.