MINIMAL BICONNECTED GRAPHS

摘要

A biconnected graph is called minimal if it becomes not biconnected after deleting any edge. We consider minimal biconnected graphs that have minimal number of vertices of degree 2. Denote the set of all such graphs on n vertices by QM(n). It is known that a graph from QM(n) contains exactly [(n+4)/3] vertices of degree 2. We prove that for k ≥ 1, the set QM(3k + 2) consists of all graphs of the type G_T, where T is a tree on k vertices the vertex degrees of which do not exceed 3. The graph G_T is constructed from two copies of the tree T: to each pair of the corresponding vertices of these two copies that have degree j in T we add 3 - j new vertices of degree 2 adjacent to this pair. Graphs of the sets QM(3k) and QM(3k +1) are described with the help of graphs G_T-Bibliography: 12 titles.