ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume


J. Bensmail

Julien Bensmail

Université Côte d'Azur



F. Mc Inerney

Fionn Mc Inerney




K. Szabo Lyngsie

Kasper Szabo Lyngsie

Technical University of Denmark




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



Discussiones Mathematicae Graph Theory 42(1) (2022) 159-185

Received: 2019-03-20 , Revised: 2019-08-28 , Accepted: 2019-08-29 , Available online: 2019-11-04 ,


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


  1. A. Ahadi, A. Dehghan and M.-R. Sadeghi, Algorithmic complexity of proper labeling problems, Theoret. Comput. Sci. 495 (2013) 25–36.
  2. T. Bartnicki, J. Grytczuk and S. Niwczyk, Weight choosability of graphs, J. Graph Theory 60 (2009) 242–256.
  3. G.J. Chang, C. Lu, J. Wu and Q. Yu, Vertex-coloring edge-weightings of graphs, Taiwanese J. Math. 15 (2011) 1807–1813.
  4. A. Davoodi and B. Omoomi, On the $1$-$2$-$3$-conjecture, Discrete Math. Theor. Comput. Sci. 17 (2015) 67–78.
  5. A. Dudek and D. Wajc, On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci. 13 (2011) 45–50.
  6. M. Karoński, T. Łuczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004) 151–157.
  7. M. Khatirinejad, R. Naserasr, M. Newman, B. Seamone and B. Stevens, Vertex-colouring edge-weightings with two edge weights, Discrete Math. Theor. Comput. Sci. 14 (2012) 1–20.
  8. H. Lu, Vertex-coloring edge-weighting of bipartite graphs with two edge weights, Discrete Math. Theor. Comput. Sci. 17 (2016) 1–12.
  9. H. Lu, Q. Yu and C.-Q. Zhang, Vertex-coloring $2$-edge-weighting of graphs, European J. Combin. 32 (2011) 21–27.
  10. K. Szabo Lyngsie, On neighbour sum-distinguishing $\{0,1\}$-weightings of bipartite graphs, Discrete Math. Theor. Comput. Sci. 20 (2018) #21.
  11. B. Seamone, The $1$-$2$-$3$ conjecture and related problems: A survey, Technical report (2012).
    arXiv: 1211.5122
  12. C. Thomassen, Graph factors modulo $k$, J. Combin. Theory Ser. B 106 (2014) 174–177.
  13. C. Thomassen, Y. Wu and C.-Q. Zhang, The $3$-flow conjecture, factors modulo $k$, and the $1$-$2$-$3$-conjecture, J. Combin. Theory Ser. B 121 (2016) 308–325.