eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2018-06-04
Vol. 20 no. 1
Graph Theory
10.23638/DMTCS-20-1-21
2632
journal article
On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite graphs
Kasper Szabo Lyngsie
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.
https://dmtcs.episciences.org/2632/pdf
Mathematics - Combinatorics