Name
Abstract | ||
|---|---|---|
The balanced decomposition number (b.d.n.) δ 0 ( Σ ) of a signed graph Σ is the smallest number of balanced subsets into which its edges can be partitioned. (A special case is decomposition of a graph into bipartite subgraphs.) The connected b.d.n. δ 1 ( Σ ) is the same, but the subsets must also be connected. The balanced partition number (b.p.n.) π 0 ( Σ ) is the smallest size of a partition of the vertices into subsets inducing balanced subgraphs; the connected b.p.n. π 1 ( Σ ) is similar but the induced subgraphs must be connected. We use signed graph coloring theory to prove that δ 0 = 1 + ⌈log 2 π 0 ⌉ and that δ 0 is analogous to a critical exponent in the sense of Crapo and Rota. We deduce bounds on δ 0 and values for special signed graphs. We show that δ 0 is computationally about as complex as the chromatic number. We prove that, for a complete signed graph, δ 1 = δ 0 ; more strongly, with three exceptions a minimal balanced decomposition exists into connected and spanning edge sets. And we show that, of δ 1 and 1 + ⌈log 2 π 1 ⌉, neither is always at least as large as the other. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1016/0095-8956(87)90026-8 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
balanced decomposition,signed graph | Discrete mathematics,Combinatorics,Modular decomposition,Line graph,Signed graph,Graph power,Distance-hereditary graph,Petersen graph,Strongly connected component,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
43 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
6 | 0.43 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. Zaslavsky | 1 | 297 | 56.67 |