Zhang, F. and X. Guo, Reducible chains in several types of 2-connected graphs, Discrete Mathematics 105 (1992) 285-291.
Let F& 4, $ and 8 denote the sets of all 2-connected graphs, minimally 2-connected graphs, critically 2-connected graphs, and critically and minimally 2-connected graphs, respectively. We introduce the concept of %,-reducible chains of a graph G in %,, i = 0, 1, 2, 3, and give the upper bound and the lower bound of a number of '??z-reducible chains of G which are both sharp. Furthermore, a construction method of 4 is obtained.
Let G = (V(G), E(G))
be a finite simple graph, and let K(G) be the connectivity of G. G is 2-connected if K(G) 3 2, G is minimally 2-connected if K(G) 2 2 but K(G -e) < 2 for any e E E(G), and G is critically 2-connected if K(G) 3 2 but K(G -V) < 2 for any u E V(G).
We denote by 9j,, %i, Y& and Y& (= 9, tl$) the sets of all 2-connected graphs, minimally 2-connected graphs, critically 2-connected graphs, and critically and minimally 2-connected graphs, respectively. We call a vertex u critical if K(G) > 2 but K(G -V) < 2. The cyclomatic number of G and the degree of a vertex v in G are denoted by v(G) and d,(v), respectively.
A satisfactory construction method of F$ can be found in Tutte's book [2]. Dirac gave a construction method of 3,. In this paper, by using the concept of Y&reducible chain, we obtain a method for constructing 3, i = 0, 1, 2, 3, and give the sharp upper and lower bounds of the number of Y&reducible chains.