Article in volume
Authors:
Title:
On {a,b}-edge-weightings of bipartite graphs with odd a,b
PDFSource:
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:
- 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 - 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 - 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 - A. Davoodi and B. Omoomi, On the $1$-$2$-$3$-conjecture, Discrete Math. Theor. Comput. Sci. 17 (2015) 67–78.
- A. Dudek and D. Wajc, On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci. 13 (2011) 45–50.
- 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 - 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 - 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 - 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 - 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 - B. Seamone, The $1$-$2$-$3$ conjecture and related problems: A survey, Technical report (2012).
arXiv: 1211.5122 - 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 - 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