Connected Graph Can Go To The Side And Algorithm Analysis

The concept of contractible edges and removable edges of graphs is a powerful tool to study the structures of graphs and to prove some properties of graphs by induction. In 1961. Tutte[6] gave the structural characterization for 3-connecfed graphs by using the existence of contractible edges and removable edges. He proved that every 3-connected graph with order at least 5 contains contractible edges. This is the earliest result concerning the concept of contractible edges and removable edges.Holton. Jackson, Wormald etc.in [3] studied the number and its distribution of the removable edges in 3-connected graph. Su .). in [4] get the sharp lower bound of removable edges in 3-connected graph and also give the structural characterization of 3-connected graphs for which the lower bound is sharp. Fouquet. Thuiller and McCuaig in [17,5] studied the removable edges in 3-cubik graph.Yin in [2] proved that there always exist removable edges in [-connected graphs G unless G is a 2-cyclic graph with order 5 or 6. There, he also showed that a 4-connected graph can be obtained from a 2-cyclic graph by the following four operations: (i) adding edges, (ii) splitting vertices, (iii) adding vertices and removing edges, and (iv) extending vertices.This thesis deals with the following three topics on graph theory and its applications: (1.) The removable edges on some subgraphs of 3-eonnected graph: (2.) The number of removable edges and its distribution on some subgraph in -1-connected graph: (3.) The arithmetic of removable edges in 3-connected graph and 4-connected graph and its analysis.The terminology and notations of graph theory, and the basic knowledge of algorithm complexity can be found in the first chapter. At the same time, we give a brief introduction of the main results of the thesis.In the first part of the thesis (chapter 2.), the distributuon of removable edges on spanning tree in 3-connected graph are studied. In this part. G is 3-connected graph, e is an edge of 3-connected graph, if G — e is a subdivisionof 3-conneeted graph, then r is called an rmuwablr edge of (.'. otherwise. < is called unremovable cdijcs of G. In this chapter, the removable edges in .'^-connected graph wen1 studied on the basement of above conclusoins. and we get the following conclusion: 1. There are at least, two removable edges on the spanning tree of 3-connected 3-regular graph; 2.7. here are at least two removable edges on the spanning tree of 3-conneeted graph with the minimum degree at least four: 3.There are at least, two removable edges on the spanning tree of 3-connected graph with the girth at least four.In the second part of the thesis (chapter 3. chapterG.). the removable edges of the 4-connected graph are studied. Let G be a 4-cotmected graph. For an edge c of G. we do the following operations on G: first, delete the edge ( from G. resulting the graph G — c: second, for all the vertices x of degree 3 in G -? (. delete x from G — < and then completely connect the 3 neighbors of x bv a triangle. If multiple edges occur, we use single edges to repla.ce them. 7'he h'nal resultant graph is denoted by 6' 6 r. If G O r is still 4-connected. then c is called a removable edge of G. otherwise, r is called an wur.mocable edges of G.In Chapter 3. The properties of the removable edges in 4-couiiecled graph are studied. The set of all removable edges of (V is denoted by Ei;(G): whereas the set ol unremovable edges of G is denoted by E,\(G).\vv get the following conclusion: (1.) Let 6" be 4-connected graph with \G\ > 7. let (.///. ,S: . 1./>') be separating group of G such that x G .4,// G D. If .1 is a edge-vertex-cut atom such that |.4| > 3. and a G S.z G A,z 7. xy G EN{G). (xij. S: A. B) be a separating group of G such that x G A.y G B. if A is a edge-vertex-cut atom of G and E(A)f)E*{G) / 0. then |.A| = 2. (3.) Let G be 4-connected graph such that \G\ > 8 and the minimum degree at least 5. then for anv ( G E(G). we have thai c is a contractible edge or r is a removabl(> edge. (1.) Let G be 4-connect.od graph such that G is not In - wheel or belt. C is a -Vcycle of G. then there1 are at least one removable edge on C.In Chapter 4. we prove that every 4-connected graph of order at least six (excluding the 2-cyclic graph of order six) has at least (4|G'j + Ki)/7 removable edges. We also give- the structural characterization of 4-connected graphs forwhich tin1 lower hound is sharp.In Chapter o and Chapter 6. the distrihutuon of removable edges oti some subgraphs in 4-comiected graph are studied.we get the following conclusions: (I) Let G be l-eonnccted graph with the girth at least four, and C be the cvcle of G. then there are two removable1 edges on C. (2) Let G be 4-cotuiected graph with the minimum degree at least five, and C be the cycle of G. then then1 arc1 two removable edges on C. (3) Let G be l-connected graph, and (' be the cycle of G which satisfying some conditions, then there arc two removable edges on C. (4) Let G be 4-connected graph, and C be the longest cycle of (7 which satisfying souk1 conditions, then there are two removable edges on ('.In the third part (chapters 7), we give a overview of the whole contents of the thesis and also propose souk1 further research problems.