# zbMATH — the first resource for mathematics

The 3-edge-components and a structural description of all 3-edge-cuts in a graph. (English) Zbl 0789.05077
Mayr, Ernst W. (ed.), Graph-theoretic concepts in computer science. 18th international workshop, WG ’92, Wiesbaden-Naurod, Germany, June 18-20, 1992. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 657, 145-157 (1993).
Summary: Let $$G=(V,E)$$ be an undirected graph, $$| V |=n$$. We denote $${\mathcal V}^ l$$ the partition of $$V$$ into maximal vertex subsets indivisible by $$k$$(-edge)-cuts, $$k<l$$, of the whole $$G$$. The factor-graph of $$G$$ corresponding to $${\mathcal V}^ 3$$, is known to give a clear representation of $${\mathcal V}^ 2$$, $${\mathcal V}^ 3$$ and of the system of cuts of $$G$$ with 1 and 2 edges. Here a (graph invariant) structural description of $${\mathcal V}^ 4$$ and of the system of 3-cuts in an arbitrary graph $$G$$ is suggested. It is based on a new concept of the 3-edge-connected components of a graph (with vertex sets from $${\mathcal V}^ 3)$$. The 3-cuts of $$G$$ are classified so that the classes are naturally 1:1 correspondent to the 3-cuts of the 3-edge-connected components. A class can be reconstructed in a simple way from the component cut, using the relation of the component to the system of 2-cuts of $$G$$. The space complexity of the description suggested is $$O(n)$$ (though the total number of 3-cuts may be a cubic function of $$n)$$.
For the entire collection see [Zbl 0866.00058].
##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C75 Structural characterization of families of graphs
##### Keywords:
graph invariant; partition; factor-graph; 3-cuts; components