Cut-set graph and systematic generation of separating sets

Abstract

In this paper an efficient method of generating separating sets of a given graph with the use of a newly defined concept-a cutset graph-is discussed. The cut-set graph of a given graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> is defined such that each edge of the graph corresponds to a pair of basic branch cut-sets of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> having the relation that the ring sum of these cut-sets coincides with an incident cut-set with respect to a vertex in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> . The present paper shows that the cut-set graph is a useful tool for solution of the problem of generating all of the basic vertex cut-sets and the basic mixed cut-sets of a given graph.