Removable Edges And Contractible Edges In Connected Graphs

The connectivity of graphs is one of the most important properties of graphs. Connected graphs plays an important role in practical applications because of its close connection with network model and combinatorial optimization. Contractible edges and removable edges are powerful tools to study the structure of graphs and to prove some properties of graphs by induction. They are very important in both theoretical respect and practical application. The main work of this paper is on removable edges and contractible edges in connected graphs in order to know more about the construction of connected graphs. This paper focus on the properties of contractible edges and removable edges in connected graphs, and their distributions in some special subgraphs of connected graphs. The following are the main results of this paper.For the removable edges in connected graphs, we give some results on the distributions of removable edges in cycles for 4-connected graphs. And for the first time, we give some results on the property of removable edges in 6-connected graphs. Key contributions are as follows:Theorem 2.2.10. Let G be a 4-connected graph and C a cycle of G. If C disjoint from any edge-vertex-cut fragment of G with the order of 2, then there are at least two removable edges in C.Theorem 2.3.2. Let G be a 6-connected graph with |G| ≥ 11 and δ(G) ≥ 7. For an edge xy ∈E_N (G), (xy,S;A,B) is the corresponding separating group, such that x ∈A, y∈ B, then E(G[S]) ∈ E_R(G). Theorem 2.3.3. Let G be a 6-connected graph with |G| ≥ 11, the order of edge-vertex cut atom in G is at least 3. For an edge xy ∈ E_N(G), (xy, S; A, B) is the corresponding separating group, such that x ∈ A, y ∈ B, then E(G[S]) (?). E_R(G).For the contractible edges in connected graphs, we give a result on the distributions of contractible edges in perfect matchings of 4-connected graphs. And for the first time, we give the distributions of contractible edges in perfect matchings of 5-connected graphs. Further more, a result on the property of contractible edges in 6-connected graphs is obtained. Key contributions are as follows:Theorem 3.2.1. Let G be a 4-connected graph with |G| > 7, M be a perfect matching of G. If there is no edge of M contained in a triangle of G, then there are at least two contractible edges in M.Theorem 3.3.2. Let G be a 5-connected graph with |G| > 9, M be a perfect matching of G. If there is no edge of M contained in a triangle of G, then there are at least two contractible edges in M.Theorem 3.3.4. Let G be a 5-connected graph with |G| > 11, M be a perfect matching of G. If the order of any fragment of G is at least 3, then there are at least two contractible edges in M.Theorem 3.4.2. Let G be a 6-connected graph with |G| ≥ 8, and the order of any end in G is not equal to 2. For a vertex x ∈ G, if there is no contractible edge incident to x, there must be a vertex y ∈ N_G(x), such that d(y) = 6 and N_G(x) ∩ N_G(y) ≠ φ hold.