DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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


Authors:

J. Bensmail

Julien Bensmail

Université Côte d'Azur

email: julien.bensmail.phd@gmail.com

0000-0002-9292-394X

F. Mc Inerney

Fionn Mc Inerney

INRIA

email: fmcinern@gmail.com

0000-0002-5634-9506

K. Szabo Lyngsie

Kasper Szabo Lyngsie

Technical University of Denmark

email: ksly@dtu.dk

0000-0002-7277-6604

Title:

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

PDF

Source:

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 , 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

References:

  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. Łuczak 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

Close