Balanced decompositions of a signed graph. (English) Zbl 0624.05056

Zaslavsky, Thomas

J. Comb. Theory, Ser. B 43, 1-13 (1987).

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.

Reviewer: H.-J.Presia

MSC:

05C75

Structural characterization of families of graphs

Keywords:

structural properties of signed graphs; balanced decomposition number; balanced partition number; balanced decompositions

References:

[1]	Cartwright, D.; Harary, F., Structural balance: A generalization of Heider’s theory, Psychol. Rev., 63, 277-293 (1956)
[2]	Crapo, H. H.; Rota, G. C., Zbl., 216, 21 (1970)
[3]	Garey, M. R.; Johnson, D. S., (Computers and Intractibility: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039
[4]	Harary, F., On the notion of balance of a signed graph, Zbl., 56, 421 (1953-1954)
[5]	Harary, F., On the measurement of structural balance, MR, 22, #3696 (1959)
[6]	Harary, F.; Hsu, D.; Miller, Z., The biparticity of a graph, Zbl., 376, 05043 (1977) · Zbl 0376.05043
[7]	Harary, F.; Kabell, J. A., A simple algorithm to detect balance in signed graphs, Zbl., 497, 05056 (1980-1981)
[8]	Matula, D. W., \(k\)-Components, clusters and slicings in graphs, Zbl., 243, 05111 (1972) · Zbl 0239.05115
[9]	Nash-Williams, C. St. J.A, Edge-disjoint spanning trees of finite graphs, Zbl., 102, 388 (1961) · Zbl 0102.38805
[10]	Tutte, W. T., On the problem of decomposing a graph into \(n\) connected factors, Zbl., 96, 380 (1961) · Zbl 0096.38001
[11]	Zaslavsky, Th, Signed graph coloring, Zbl., 487, 05027 (1982) · Zbl 0487.05027
[12]	Zaslavsky, Th, How colorful the signed graph?, Zbl., 554, 05026 (1984) · Zbl 0554.05026