Removable Edges, Cycles And Connectivity In Graphs

Graph theory is a very important research field of discrete mathematics. It is widely applied in various disciplines, such as computer science, chemistry, social science and biology etc.Since Tutte gave a construction of 3-connected graphs in 1961, research on structural characterizations of graphs becomes a very popular topic in graph theory. It plays an important role in both theoretical respect and practical applications due to its close connection to network modeling and combinatorial optimization. The concepts of contractible edges and removable edges of graphs are powerful tools to study the structure of graphs and to prove properties of graphs by induction. From Chapter 2 to Chapter 4, we focus on the the existence of contractible edges and the distribution of removable edges in certain substructures of connected graphs.In Chapter 2, we focus on the property of contractible edges in k-connected graphs without triangles. Let G be a k-connected graph and e= uv an edge of G. By G/e we denote the graph obtained from G by deleting the vertices u, v and adding a new vertex ve such that ve is adjacent to all the former neighbors of u and v. If G/e is still k-connected, then e is called a k-contractible edge. A noncomplete k-connected graph G is called an contraction critically k-connected graph if G has no k-contractible edges. For k = 3, Tutte [83] proved that every 3-connected graph with order at least 5 has a 3-contractible edge. For k=4, Martinov and Fontet proved that any contraction critically 4-connected graph is either Cn2 or the line graph of a cubic (7/2)-connected graph [32] [59]. Here, the cubic (7/2)-connected graphs can be obtained in a constructive way from K4 or the cube K(4,4)-(1-factor). For the case k≥5, it has been proved that the class of contraction critically 5-connected graphs is rich. So substructure properties of contraction critically k-connected graphs have been investigated. In 1982, Thomassen [81] got that every contraction critically k-connected graph contains a triangle, that is to say, if a k-connected graph G has no triangles, then G has an edge e= uv such that no k-vertex-cuts contain both u and v. Recently, Fujita etc. [37] presented a result which stated that, if the minimum degree of k-connected graph G is at least [3k/2]+2, then G has a contractible edge e= uv such that G -{u, v} is still k-connected. Combining the above two results, we prove the following conclusion, meanwhile, we give examples to show the minimum degree condition is necessary. Conclusion 1 Let G be a k(k≥2)-connected triangle-free graph withδ(G)≥k+1. Then G has an edge e such that G - V(e) is still k-connected.For removable edges of k-connected graphs, in 1990, Holton etc. [39] first defined removable edges in a 3-connected graph. Later, Yin [93] defined removable edges in a 4-connected graph. Recently, Xu [91] generalized the concept of remov-able edges in a 3-connected graph and a 4-connected graph to k-connected graphs. Let G be a k-connected graph, and let e be an edge of G. Let G (?) e denote the graph obtained from G by the following operation:(1) delete e from G to get G - e; (2) for any end vertex of e with degree k - 1, say x, delete x, and then add edges between any pair of non-adjacent vertices in N(G-e)(x)-If G(?)e is k-connected, then e is said to be a removable edge of G. The set of all removable edges is denoted by ER(G). Early in 1966, Barnette etc. [12] proved that a 3-connected graph of order at least five has a removable edge and gave a construction of 3-connected graphs. This is the earliest result about the removable edges. In [93], Yin proved that the 4-connected graph without removable edges is either C52 or C62. Based on this result, he provided a constructive characterization of 4-connected graphs, which is much simpler than Slater's method [71]. After defining removable edges in k-connected graphs, Xu etc. [91] [92] proved that the 5-connected graph without re-movable edges is K6. Meanwhile, they conjectured that, for a k(k≥3)-connected graph G, G has no removable edge if and only if either G(?) K(k+1) for k being odd, or G is isomorphic to either K(k+1) or H((k+2)/2) for k being even. Recently, the conjecture was verified to be true by Su etc. [76]. So the problem of the existence of removable edges is resolved. On the other hand, the distribution of removable edges in certain substructure of connected graph also attracts much attention.In Chapter 3, we investigate the distribution of removable edges in 3-connected graphs. Su [72] proved that the distribution of removable edges on a Hamilton cy-cle of 3-connected graphs depends on the number of maximal semiwheels. We generalize the result to longest cycles in 3-connected graphs. Wu etc. [43] [88] provided the results which stated that, there are at least two removable edges in or off any spanning tree of a 3-connected 3-regular graph. We also improve the results. Using the properties of removable edges in 3-connected graphs, we prove that Thomassen's conjecture (every longest cycle in a 3-connected graph has a chord) is true for two classes of 3-connected graphs, in adition, we give examples to show that these classes are not covered by previous results. Now, we list the conclusions of this chapter.Conclusion 2 Let G be a 3-connected graph distinct from wheels with|G|≥6 and C a longest cycle. Then(1) If C does not pass through any maximal semiwheel, then C contains at least three removable edges;(2) If C passes through precisely one maximal semiwheel, then C contains at least two removable edges;(3) If C passes through precisely two maximal semiwheels, then C contains a re-movable edge.Conclusion 3 Let G be a 3-connected graph without any maximal semiwheels and let T be a spanning tree of G. Then there are at least two removable edges in or off T.Conclusion 4 Let G be a 3-connected graph on at least 6 vertices and let C be a longest cycle of G. If|E(C)∩ER(G)|≤5, then C has a chord.Conclusion 5 Let G be a 3-connected graph on at least 9 vertices and let C be a longest cycle of G. If|(E(G)-E(C))∩ER(G)|≤7 and there is no atom of G vertex-disjoint with C, then C has a chord.In Chapter 4, we focus on the distribution of removable edges in 5-connected graphs. For 5-connected graphs G, Xu got that, ifδ(G)≥6 or g(G)≥4 or G has no atoms, then any cycle contains at least two removable edges in G; ifδ(G)≥6 or g(G)≥4, then any spanning tree of G contains at least two removable edges. We extend these results.Conclusion 6 Let G be a 5-connected graph with order at least 8. Then any triangle contains a removable edge.Conclusion 7 Let G be a 5-connected graph with order at least 10 and C a cycle of G. Then(1) If C is vertex-disjoint with any atom, then C contains two removable edges;(2) If C has common vertices with precisely one atom, then C contains a removable edge;(3) If G contains no atoms and C is a Hamilton cycle, then C contains at least three removable edges;(4) If d(x)+d(y)≥11 for any pair of adjacent vertices x, y in G, then C contains two removable edges.Conclusion 8 Let G be a 5-connected graph with order at least 10 and T a spanning tree of G. If G contains no atoms, then T contains at least two removable edges.The last part of the thesis is devoted to the prism cyclability of graphs. The prism over a graph G is the Cartesian product G□K2 of G with the complete graph K2. G is said to be prism hamiltonian if G□K2 is hamiltonian. We say that a set H (?) V(G) of vertices is cyclable in G if there is a cycle C in G containing all vertices of H. For H (?) V(G), we say that H is prism cyclable in GDK2 if H U H' where H' is the copy of H is cyclable in G□K2. The hunt for Hamilton cycles in graphs is one of the oldest and also one of the most investigated topics in graphs. Since the concept was formally introduced by Hamilton in 1857, there have been a large number of theorems, conjectures (both open and refuted), surveys, and web sites dedicated to this hunt. One of the recent trends is to find variations on the notion of a Hamilton cycle for testing how " close " a given graph G is to being hamiltonian. The graph with the property of being prism hamiltonian is such a variation. Recently, Ozeki [65] investigated the degree sum condition for the graph to be prism hamiltonian and proved that, for a connected graph G with order n≥2, ifσ3(G)≥n, then G is prism hamiltonian. We localize the result to the general case, which is about prism cyclability. We also consider the prism cyclability in claw-free graphs.Conclusion 9 Let G be a connected graph, n=|V(G)|≥2, (?)≠S (?) V(G), S is 1G-connected. Ifσ3(S)≥n, then S is prism cyclable in G□K2.Conclusion 10 Let G be a graph of order n≥2 and let S (?) V(G), S≠(?), be such that(ⅰ) S is 1G-connected,(ⅱ) no vertex in S∪N(S) is a claw center,(ⅲ)σ3(S)≥n - 3 (considered in G). Then S is prism cyclable in G□K2 or S is a (a, b, c)-part structure.