The balanced properties of bipartite graphs with applications (Q2715962)

If \(G=(V,E)\) is a simple graph and \(g:V\rightarrow \{0,1,\ldots , |E|\}\) an injection, one can define an induced map \(g^* : E \rightarrow \{1,2,\ldots ,|E|\}\) by \(g^* (uv) = |g(u) - g(v)|\) for \(uv \in E\). If \(g^*\) is a bijection, then \(g\) is said to be a graceful labeling of \(G\), and \(G\) itself is said to be graceful. If \(g\) is a graceful labeling of \(G\) and there exists a number \(c\) such that \(g(n) \leq c\) and \(g(v) > c\) for all \(uv \in E\), then \(G\) is said to be balanced. NEWLINENEWLINENEWLINEThe author considers mainly graphs of two types: (a) \(C_m(n)\) is the connected graph \(n\) blocks of which are the cycles \(C_m\) and the block-cutpoint graph is a path, and (b) \(n C_m\) is the disjoint union of \(n\) cycles \(C_m\). NEWLINENEWLINENEWLINEDeveloping further results of J.~Abrham and A.~Kotzig, he presents certain properties of balanced labelings and proves that, for all \(m,n \geq 1\), \(C_{4m} (n)\) and \(((m+1)^2+1)C_4\) are balanced, whereas \(C_{4m+3}(n)\) and \(C_{4m+1} (n)\) are not.