Minimally Connected Graphs Of Low Order

Let G be a connected graph.If to disconnect G we have to delete at least k vertices,then the connectivity of G is defined to be k.A graph is called k-connected if its connectivity is at least k.For a k-connected graph G,if deleting any edge of G decreases strictly its connectivity,then G is called minimally k-connected.Minimally 1-connected graphs are just trees.Hence in this thesis we consider graphs of connectivity at least2.Two isomorphic graphs are regarded as the same graph.Thus the number of graphs in a class means the number of pair-wise nonisomorphic graphs in the class.In this thesis we determine all the minimally 2-connected graphs,minimally 3-connected graphs,minimally4-connected graphs of order at most 8,and consequently we obtain the number of graphs in each of these classes.In the proofs,we have used several important results: An upper bound on the size of minimally k-connected graphs of order n,a lower bound on the number of vertices of degree k in a minimally k-connected graph of order n,a necessary condition for the degree sequence of k-connected graphs,and properties of minimally k-connected graphs with k=43,2,.