On neighbour sum-distinguishing {0,1}-weightings of bipartite graphs

Kasper Szabo Lyngsie*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

64 Downloads (Pure)

Abstract

Let S ⊂ Z 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.
Original languageEnglish
Article number21
JournalDiscrete Mathematics and Theoretical Computer Science (Online Edition)
Volume20
Issue number1
Number of pages23
ISSN1365-8050
DOIs
Publication statusPublished - 2018

Keywords

  • 1-2-3-Conjecture
  • Neighbour-sum-distinguishing edge-weightings
  • Bipartite graphs

Fingerprint Dive into the research topics of 'On neighbour sum-distinguishing {0,1}-weightings of bipartite graphs'. Together they form a unique fingerprint.

Cite this