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

Kasper Szabo Lyngsie

doi:10.23638/DMTCS-20-1-21

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

Kasper Szabo Lyngsie^*

^*Corresponding author for this work

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

235 Downloads (Orbit)

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 language	English
Article number	21
Journal	Discrete Mathematics and Theoretical Computer Science (Online Edition)
Volume	20
Issue number	1
Number of pages	23
ISSN	1365-8050
DOIs	https://doi.org/10.23638/DMTCS-20-1-21
Publication status	Published - 2018

Keywords

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

Access to Document

10.23638/DMTCS-20-1-21

1701Final published version, 1 MB

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{7eafd2ef541b4357a7f749ee8dcaa9a5,

title = "On neighbour sum-distinguishing \{0,1\}-weightings of bipartite graphs",

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. ",

keywords = "1-2-3-Conjecture, Neighbour-sum-distinguishing edge-weightings, Bipartite graphs",

author = "Lyngsie, \{Kasper Szabo\}",

year = "2018",

doi = "10.23638/DMTCS-20-1-21",

language = "English",

volume = "20",

journal = "Discrete Mathematics and Theoretical Computer Science (Online Edition)",

issn = "1365-8050",

publisher = "Maison de l'informatique et des mathematiques discretes",

number = "1",

}

TY - JOUR

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

AU - Lyngsie, Kasper Szabo

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - 1-2-3-Conjecture

KW - Neighbour-sum-distinguishing edge-weightings

KW - Bipartite graphs

U2 - 10.23638/DMTCS-20-1-21

DO - 10.23638/DMTCS-20-1-21

M3 - Journal article

SN - 1365-8050

VL - 20

JO - Discrete Mathematics and Theoretical Computer Science (Online Edition)

JF - Discrete Mathematics and Theoretical Computer Science (Online Edition)

IS - 1

M1 - 21

ER -

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

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this