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