DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

Article in press


Authors:

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

Title:

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

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-03-20, Revised: 2019-08-28, Accepted: 2019-08-29, https://doi.org/10.7151/dmgt.2250

Abstract:

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.

Keywords:

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

PDF
Close