Brick partitions of graphs

For each rational number q = b/c where b >= c are positive integers, we define a q-brick of G to be a maximal subgraph H of G such that cH has b edge-disjoint spanning trees, and a q-superbrick of G to be a maximal subgraph H of G such that cH - e has b edge-disjoint spanning trees for all edges e of cH, where cH denotes the graph obtained from H by replacing each edge by c parallel edges. We show that the vertex sets of the q-bricks of G partition the vertex set of G, and that the vertex sets of the q-superbricks of G form a refinement of this partition. The special cases when q = 1 are the partitions given by the connected components and the 2-edge-connected components of G, respectively. We obtain structural results on these partitions and describe their relationship to the principal partitions of a matroid. (C) 2008 Elsevier E.V. All rights reserved.