The Tree of Cuts and Minimal k-Connected Graphs

Abstract

A cut of a k-connected graph G is a k-element cutset of it, which contains at least one edge. The tree of cuts of a set, consisting of pairwise independent cuts of a k-connected graph, is defined in the following way. Its vertices are the cuts of the setand the parts of the decomposition of G induced by these cuts. A part A is adjacent to a cut S if and only if A contains all the vertices of S and exactly one end of each edge of S. It is proved that the defined graph is a tree, some properties of which are similar to the corresponding properties of the classic tree of blocks and cutpoints.

In the second part of the paper, the tree of cuts is used to study minimal k-connected graphs for k ≤ 5. Bibliography: 11 titles.