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

dmtcs:4554 - Discrete Mathematics & Theoretical Computer Science, June 4, 2018, Vol. 20 no. 1
On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite graphs

Authors: Lyngsie, Kasper Szabo

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.


Source : oai:arXiv.org:1701.00927
DOI : 10.23638/DMTCS-20-1-21
Volume: Vol. 20 no. 1
Section: Graph Theory
Published on: June 4, 2018
Submitted on: January 5, 2017
Keywords: Mathematics - Combinatorics


Share

Consultation statistics

This page has been seen 55 times.
This article's PDF has been downloaded 16 times.