Technical Report CS757

TR#:CS757
Title: THE 3-EDGE-COMPONENTS AND A STRUCTURAL DESCRIPTION OF ALL 3-EDGE-CUTS IN A GRAPH.
Authors: E. Dinitz
PDFNot Available
Abstract:

Let G=(V,E) be an undirected graph, |V|=N. We denote {\Cal 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 {\Cal V}^3, is known to give a clear representation of {\Cal V}^2, {\Cal V}^3 and of the system of cuts of G with 1 and 2 edges. Here a (graph invariant) structural description of {\Cal 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 {\Cal 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. For 3-cuts and {\Cal V}^4 of a 3-edge-connected graph, we follow [DKL76]. The space complexity of the description suggested is O(n) (though the total number of 3-cuts may be a cubic function of n).

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1992/CS/CS0757), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1992
To the main CS technical reports page

Computer science department, Technion