ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


J. Bensmail, F. Mc Inerney, K. Szabo Lyngsie


On $\{a,b\}$-edge-weightings of bipartite graphs with odd $a,b$


Discussiones Mathematicae Graph Theory

Received: 2019-03-20, Revised: 2019-08-28, Accepted: 2019-08-29,


For any $S \subset \mathbb{Z}$ we say that a graph $G$ has the $S$-property if there exists an $S$-edge-weighting $w: E(G) \rightarrow S$ such that for any pair of adjacent vertices $u,v$ we have $\sum_{e\in E(v)}w(e) \neq \sum_{e\in 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 \in \mathbb{Z}$ 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 \neq -1$, while there is an easy characterization of trees without the $\{-1,1\}$-property.


neighbour-sum-distinguishing edge-weightings, bipartite graphs, odd weights, 1-2-3 conjecture