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

dmtcs:2632 - Discrete Mathematics & Theoretical Computer Science, June 4, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-21
On neighbour sum-distinguishing {0,1}-edge-weightings of bipartite graphsArticle

Authors: 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)→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://doi.org/10.23638/DMTCS-20-1-21
    Source: arXiv.org:1701.00927
    Volume: Vol. 20 no. 1
    Section: Graph Theory
    Published on: June 4, 2018
    Accepted on: May 21, 2018
    Submitted on: January 5, 2017
    Keywords: Mathematics - Combinatorics
    Licence: arXiv.org - Non-exclusive license to distribute

    Share and export

    Consultation statistics

    This page has been seen 622 times.
    This article's PDF has been downloaded 308 times.