{"docId":4554,"paperId":2632,"url":"https:\/\/dmtcs.episciences.org\/2632","doi":"10.23638\/DMTCS-20-1-21","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":324,"name":"Vol. 20 no. 1"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"1701.00927","repositoryVersion":3,"repositoryLink":"https:\/\/arxiv.org\/abs\/1701.00927v3","dateSubmitted":"2017-01-05 11:52:30","dateAccepted":"2018-06-04 10:26:58","datePublished":"2018-06-04 10:27:12","titles":["On neighbour sum-distinguishing $\\{0,1\\}$-edge-weightings of bipartite graphs"],"authors":["Lyngsie, Kasper Szabo"],"abstracts":["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) \\rightarrow 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.","Comment: Journal version"],"keywords":["Mathematics - Combinatorics"]}