Geodesic
On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 159-185.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: neighbour-sum-distinguishing edge-weightings, bipartite graphs, odd weights, 1-2-3 Conjecture 
@article{DMGT_2022_42_1_a10,
     author = {Bensmail, Julien and Inerney, Fionn Mc and Lyngsie, Kasper Szabo},
     title = {On {a, {b}-Edge-Weightings} of {Bipartite} {Graphs} with {Odd} a, b},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {159--185},
     publisher = {mathdoc},
     volume = {42},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a10/}
}
TY  - JOUR
AU  - Bensmail, Julien
AU  - Inerney, Fionn Mc
AU  - Lyngsie, Kasper Szabo
TI  - On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 159
EP  - 185
VL  - 42
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a10/
LA  - en
ID  - DMGT_2022_42_1_a10
ER  - 
%0 Journal Article
%A Bensmail, Julien
%A Inerney, Fionn Mc
%A Lyngsie, Kasper Szabo
%T On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 159-185
%V 42
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a10/
%G en
%F DMGT_2022_42_1_a10
Bensmail, Julien; Inerney, Fionn Mc; Lyngsie, Kasper Szabo. On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 159-185. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a10/

[1] A. Ahadi, A. Dehghan and M.-R. Sadeghi, Algorithmic complexity of proper labeling problems, Theoret. Comput. Sci. 495 (2013) 25–36. https://doi.org/10.1016/j.tcs.2013.05.027

[2] T. Bartnicki, J. Grytczuk and S. Niwczyk, Weight choosability of graphs, J. Graph Theory 60 (2009) 242–256. https://doi.org/10.1002/jgt.20354

[3] G.J. Chang, C. Lu, J. Wu and Q. Yu, Vertex-coloring edge-weightings of graphs, Taiwanese J. Math. 15 (2011) 1807–1813. https://doi.org/10.11650/twjm/1500406380

[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. Luczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004) 151–157. https://doi.org/10.1016/j.jctb.2003.12.001

[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. https://doi.org/10.46298/dmtcs.570

[8] H. Lu, Vertex-coloring edge-weighting of bipartite graphs with two edge weights, Discrete Math. Theor. Comput. Sci. 17 (2016) 1–12. https://doi.org/10.46298/dmtcs.2162

[9] H. Lu, Q. Yu and C.-Q. Zhang, Vertex-coloring 2 -edge-weighting of graphs, European J. Combin. 32 (2011) 21–27. https://doi.org/10.1016/j.ejc.2010.08.002

[10] K. Szabo Lyngsie, On neighbour sum-distinguishing {0, 1} -weightings of bipartite graphs, Discrete Math. Theor. Comput. Sci. 20 (2018) #21. https://doi.org/10.23638/DMTCS-20-1-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. https://doi.org/10.1016/j.jctb.2014.01.002

[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. https://doi.org/10.1016/j.jctb.2016.06.010