Affordable Access

Access to the full text

On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b

Authors
  • Bensmail, Julien1
  • Inerney, Fionn Mc1
  • Lyngsie, Kasper Szabo
  • 1 CNRS, Inria, I3S , (France)
Type
Published Article
Journal
Discussiones Mathematicae Graph Theory
Publisher
Sciendo
Publication Date
Dec 17, 2021
Volume
42
Issue
1
Pages
159–185
Identifiers
DOI: 10.7151/dmgt.2250
Source
De Gruyter
Keywords
License
Green

Abstract

For any S ⊂ ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w : E(G) → S such that for any pair of adjacent vertices u, v we have ∑e∈E(v) w(e) ≠ ∑e∈E(u) w(e), where E(v) and E(u) are the sets of edges incident to v and u, respectively. This work focuses on {a, a + 2}-edge-weightings where a ∈ ℤ is odd. We show that a 2-connected bipartite graph has the {a, a + 2}-property if and only if it is not a so-called odd multi-cactus. In the case of trees, we show that only one case is pathological. That is, we show that all trees have the {a, a + 2}-property for odd a ≠ −1, while there is an easy characterization of trees without the {−1, 1}-property.

Report this publication

Statistics

Seen <100 times