The Distributions Of Contractible Edges In Connected Graphs

The connectivity of the graphs is one of the basic properties and is the most important issue in the graphs. Connected graphs play an important role in practical applications. And it is closely connected with network model and combinatorial optimization. Discussing the structure characteristics of connected graph has always been one of advanced problem in graph theory. In order to make any. connected graph can be repeated by some simple connected graphs, the operation of being connected of graphs are introduced. Contractible edges are powerful tools to study the structure of the graphs and to prove some properties of the graphs by induction. They are very important in theoretical respect and practical application.Let G=(V(G), E(G)) be a connected graph, and let V’ be a subset of V(G). We call V’ a vertex cut of G if G - V’ is disconnected. A k-vertex cut is a vertex set of k elements. If G has at least one pair of distinct nonadjacent vertices, the connectivity k(G) of G is the minimum k for which G has a k-vertex set; otherwise, we define k(G) to be v(G) - 1. G is said to be k-connected if k(G)> k. To contract an edge e of a graph G is to delete the edge and then identify its ends. The resulting graph is denoted by G/e. Let G be a 7-connected graph, and let e be an edge of G. If G/e is 7-connected, then e is called contractible edge. In 2003, Wu Jichang and Li Xueliang gave the distribution of the contractible edge in 4-connected graphs. Recently, the distributions of the contractible edges in 5-connected graph and 6-connected graphs were given. In this paper, we will prove these results in 7-connected graphs.In this paper, we will give the distributions of the contractible edges in the longest cycles and the perfect matchings of 7-connected graphs.This paper is mainly composed of four chapters. In the first chapter, we simply introduce the history and development of graph theory.In the second chapter, several useful concepts on graphs are given.In the third chapter, we show that the distributions of contractible edges on longest cycles of 7-connected graphs. The result is as follows:(i) Let G be a 7-connected graph, and let P = (x=)x1X2 … xt(= y) be a longest (x, y)-path of G for any vertex pair x, y ∈ V(G). For any vertex set S of order 7, if there exists a end-fragment in G — S, then there is at least one contractible edge in E(P).(ii) Let G be a 7-connected graph, and let C be the most longest cycle of G. If there exists a end-fragment in G — S, for any vertex set S of order 7, then there are at least two contractible edges in C.In the fourth chapter, we give the distributions of contractible edges in perfect matchings of 7-connected graphs. The results are as follows:(i) Let G be a 7-connected graph, let M be a perfect matching of G, and let C0 be an arbitrary cycle with length 3 < |V(C0)| < 5 of G. For any vertex set S of order 7, if there exists a end-fragment in G — S, and e (?) E(C0) for any e € M, then there is at least one contractible edge in M.(ii) Let G be a 7-connected graph with girth g(G) > 5, and let M be a perfect matching of G. For any vertex set S of order 7, if there exists a end-fragment in G — S, then there are at least two contractible edges in M.