On \(\{a, b\}\)-edge-weightings of bipartite graphs with odd \(a, b\) (Q2062679)

This paper studies \(\{a, b\}\)-properties where both \(a\) and \(b\) are odd integers, specially for bipartite graphs with \(b=a+2\). If each vertex \(v \in V (G)\) of a graph \(G\) has weighted degree equal to the sum of the weights of its incident edges such that \(w : E(G) \to S; S\subset \mathcal{Z}\) (the set of integers), then it is said to have \(S\)-edge-weighting. \(G\) has \(S\)-property implies any two adjacent vertices have distinct \(S\)-edge-weightings. Here, we consider \(S= \{a,b\}\). This paper concentrates on bipartite graphs because the 1-2-3 conjecture holds for them, the NP-completeness results related to \(S\)-property are not applicable to them. It is observed that the study of the \(\{a,b\}\)-property is relevant when \(a\) and \(b\) are relatively prime. This article includes 2 main theorems, 9 lemmas, 4 observations, 8 claims and a definition. This paper consists of three sections: the introduction, the proof of Theorem 1 and the proof of Theorem 2. The introductory section defines the \(S\)-property, a review of the literature of classes of graphs with the \(\{a,b\}\) property, the statements of the two theorems proved in this paper, two operations of constructing graphs without the \(\{-1, 1\}\)-property from graphs without this property. The second section is a lengthy one which proves Theorem 1 with the help of some claims and observations. The third section proves that one of the operations explained in the first section can be used to construct trees without the \(\{-1, 1\}\)-property. The third author [Discrete Math. Theor. Comput. Sci. 20, No. 1, Paper No. 21, 23 (2018; Zbl 1401.05136)] constructed the multi-cactus, which is the concept extensively described in the paper, in one of his previous papers as follows: From a collection of cycles, whose edges are alternatively colored with red and green, of length 2 modulo 4, form a connected simple graph by pasting the cycles along green edges, one by one in a tree-like manner. \(K_2\) is an odd multi-cactus with a single green edge too. Replacing a green edge of an odd multi-cactus with multiple parallel green edges also results in an odd multi-cactus [loc. cit.]. Note that \(K_2\) is the only tree without the \(\{a, b\}\)-property, where both \(a,b \in \mathcal{Z^+}\) or both \(a,b \in \mathcal{Z^-}\). Among the two theorems of the paper, the first theorem proves that the class of 2-connected bipartite graphs without \(\{a, a+2\}\)-property is the same as that of odd multi-cactus, where \(a\) is an odd integer. The proof technique involves the method of two-coloring of edges into red and green colors, where parallel edges are colored with the same color. To prove certain claims followed by first theorem, blue edges are used for the edges of certain paths (known as suspended paths) and white edges for the remaining edges. Claim 19, whose proof needs almost three pages, says that for every vertex \(v\) of \(H\), we have \(d_{G^\ast} (v) = 3\), where the bipartite multigraph \(G^*\) is obtained by replacing all the suspended paths of length \(3\) (the blue edges) by edges and \(H\) is a component of \(G^\ast\). The only definition introduced in this paper is about mod 4 vertex-colouring of a graph \(G\), which is a vertex coloring \(c : V (G) \to \{1, 2\}\) of \(G\) satisfying the following conditions for any \(uv \in E(G)\) where \(d(u)\) and \(d(v)\) have the same parity: i) \(d(u) \equiv d(v) \pmod 4\) \(\implies c(u) \neq c(v)\), ii) \(d(u) \not\equiv d(v) \pmod 4\) \(\implies c(u) = c(v)\). One of the lemmas proved that every bipartite graph has a mod 4 vertex-colouring. One of the major observations (which is referred around \(16\) times thereafter) appears in this paper as follows: Let \(a\) and \(b\); \(b=a+2\) be two odd integers, the edges of the graph \(G\) be weighted with \(a\) and \(b\) and \(uv\) be an edge in \(G\). If any one of the following is satisfied: i) \(d(u)\) and \(d(v)\) have distinct parity, or ii) \(d(u) \equiv d(v) \pmod 4\) and \(v\) is incident to an odd number of \(a\)-edges while \(u\) is incident to an even number of \(a\)-edges, or iii) \(d(u) \not\equiv d(v) \pmod 4\) and both \(v\) and \(u\) are incident to an odd or even number of \(a\)-edges, then \(u\) and \(v\) have distinct weighted degrees. This is true irrespective of the parity of the number of incident \(a\)-edges or \(b\)-edges that are considered. The second theorem is that a tree does not have the \(\{-1, 1\}\)-property if and only if it can be constructed from a disjoint union of \(K_2\)'s through repeated applications of the first operation explained in the introduction. The authors uses different proof methods such as the methods of induction and deduction, the method of contradiction, and the method of contrapositives and also coloring techniques to prove various results in the paper. This study helps us to look to bipartite graphs and weighted graphs from another point of view.