Balanced decompositions of a signed graph (Q1092068)

All edges of a signed graph are labelled positive or negative and it is balanced if every circuit has a positive sign product. It is introduced the balanced decomposition number (b.d.n.) \(\delta_ 0\) as a measure of imbalance for signed graphs: the smallest number of balanced subsets into which the edge set can be partitioned. \(\delta_ 0\) passes into the connected b.d.n. \(\delta_ 1\) if those subsets are connected. Also are defined the balanced partition number (b.p.n.) \(\pi_ 0\) and the connected b.p.n. \(\pi_ 1\) of a signed graph: the smallest number of sets into which the vertices of this graph can be partitioned so that each set induces a balanced (connected) subgraph. The subject of the main theorem which is proved by using certain methods of coloring signed graphs is the interesting relation between \(\delta_ 0\) and \(\pi_ 0\), namely \(\delta_ 0=1+\lceil \log_ 2\pi_ 0\rceil\) and it is also proved that \(\delta_ 0\) is analogous to a critical exponent in the sense of Crapo and Rota (\(\lceil n\rceil\) denotes the smallest integer \(\geq n)\). Furthermore in this article are given bounds on \(\delta_ 0\) and values of special graphs and it is proved that holds \(\delta_ 0=\delta_ 1\) for complete signed graphs. But the analogous relation between the quantities \(\delta_ 1\) and \(\pi_ 1\) does not exist in general, it is shown by examples that they also are related by an inequality in either direction. Finally it is referred to more highly connected balanced decompositions by examples.