Abstract
Let S ⊂ Z be a set of integers. A graph G is said to have the S-property if there exists an S-edge-weighting w : E(G) → S such that any two adjacent vertices have different sums of incident edge-weights. In this paper we characterise all bridgeless bipartite graphs and all trees without the {0,1}-property. In particular this problem belongs to P for these graphs while it is NP-complete for all graphs.
Original language | English |
---|---|
Article number | 21 |
Journal | Discrete Mathematics and Theoretical Computer Science (Online Edition) |
Volume | 20 |
Issue number | 1 |
Number of pages | 23 |
ISSN | 1365-8050 |
DOIs | |
Publication status | Published - 2018 |
Keywords
- 1-2-3-Conjecture
- Neighbour-sum-distinguishing edge-weightings
- Bipartite graphs