On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite graphs

Abstract

Let $S$ 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)\to 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.

Journal version

References in corpus (1)

• The 1-2-3 Conjecture and related problems: a survey