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 GM(n). It is known that a graph from GM(n) contains exactly (formula presented)vertices of degree 2. We prove that for k ≥ 1, the set GM(3k + 2) consists of all graphs of the type GT, where T is a tree on k vertices the vertex degrees of which do not exceed 3. The graph GT 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 GM(3k) and GM(3k+1) are described with the help of graphs GT. Bibliography: 12 titles.

Original languageEnglish
Pages (from-to)244-257
Number of pages14
JournalJournal of Mathematical Sciences (United States)
Volume204
Issue number2
Early online date9 Dec 2014
DOIs
StatePublished - 2015

    Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Applied Mathematics

    Research areas

  • Pairwise Disjoint, Terminal Part, Decomposition Tree, Vertex Degree, Boundary Vertex

ID: 36925352