TR#:  CS757 
Title:  THE 3EDGECOMPONENTS AND A STRUCTURAL DESCRIPTION OF ALL 3EDGECUTS IN A GRAPH. 
Authors:  E. Dinitz 
PDF  Revised  CS0757.revised.pdf 
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 factorgraph 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 3cuts in an arbitrary graph G is suggested. It is based on a new concept of the 3edgeconnected components of a graph (with vertex sets from {\Cal V}^3). The 3cuts of G are classified so that the classes are naturally 1:1 correspondent to the 3cuts of the 3edge 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 2cuts of G. For 3cuts and {\Cal V}^4 of a 3edgeconnected graph, we follow [DKL76]. The space complexity of the description suggested is O(n) (though the total number of 3cuts may be a cubic function of n).

Copyright  The 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/cgibin/trinfo.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