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

Emma Barme, Julien Bensmail, Jakub Przybyło, Mariusz Wozniak

Research output: Contribution to journalJournal articleResearchpeer-review

155 Downloads (Pure)

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.
Original languageEnglish
JournalDiscrete Applied Mathematics
Volume217
Issue numberPart 2
Pages (from-to)123-131
ISSN0166-218X
DOIs
Publication statusPublished - 2017

Keywords

  • 1-2-3 Conjecture
  • 1-2 Conjecture
  • Diagraphs

Fingerprint Dive into the research topics of 'On a directed variation of the 1-2-3 and 1-2 Conjectures'. Together they form a unique fingerprint.

Cite this