Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649168 | Discrete Mathematics | 2010 | 6 Pages |
For each rational number q=b/cq=b/c where b≥cb≥c are positive integers, we define a qq-brick of GG to be a maximal subgraph HH of GG such that cHcH has bb edge-disjoint spanning trees, and a qq-superbrick of GG to be a maximal subgraph HH of GG such that cH−ecH−e has bb edge-disjoint spanning trees for all edges ee of cHcH, where cHcH denotes the graph obtained from HH by replacing each edge by cc parallel edges. We show that the vertex sets of the qq-bricks of GG partition the vertex set of GG, and that the vertex sets of the qq-superbricks of GG form a refinement of this partition. The special cases when q=1q=1 are the partitions given by the connected components and the 2-edge-connected components of GG, respectively. We obtain structural results on these partitions and describe their relationship to the principal partitions of a matroid.