The Contractible Edges In The 5-connected And 7-connected Graphs

Graph connectivity is one of the important graph theory concepts, which is closely related to many graph properties. In the study of graph theory, we often use the properties of some graph operations to construct complex connected graph, which satisfies the requirements of properties, with some simple connected graphs. Based on this theory, contractible edge operation has become one of the powerful tools for the study of complex connected graphs.In this paper, we select the connected graph contractible edges as the object of study, considering the distribution of contractible edges in particular subgraph - the longest cycle, spanning tree and perfect matching of the 5-connected and 7-connected graphs, and obtain the corresponding results.For 5-connected graph, this paper improves the achievement of the distribution of contractible edges in the longest cycle of 5-connected graphs, and proposed the distribution of contractible edges in the spanning tree of 5-connected graphs for the first time. The main conclusions are as follows:Theorem 2.1.3 Let G be a 5-connected graph without 2-fragment, P:x= x1x2…-xn= y a longest (x,y)-path of G.If any vertex of P satisfies one of the following conditions, P contains at least two contractible edges: (1)d(xi)≥6;(2) d(xi)=5, there is no 3-cycle contains it.Theorem 2.2.1 Let G be a 5-connected graph without 2-fragment, H a spanning tree of G. If any vertex of H satisfies one of the following conditions, H contains at least two contractible edges: (1)d(xi)≥6;(2) d(xi)= 5, there is no 3-cycle contains it.For 7-connected graph, this paper still use tree structure theory to proof the theorem, and discusses the distribution of contractible edges in the longest cycle, spanning tree and perfect matching of the 7-connected graphs, obtain the corresponding results.Theorem 3.1.5 Let G be a 7-connected graph, and the order of fragment in G is at least 3. If C is the longest cycle of G, C contains at least three contractible edges.Theorem 3.2.1 Let G be a 7-connected graph, and the order of fragment in G is at least 3. If H is a spanning tree of G, H contains at least two contractible edges.Theorem 33.7 Let G be a 7-connected graph with |G|>15, M be a perfect matching. There is no edge of M contained in a triangle of G, then M contains at least two contractible edges.Theorem 33.8 Let G be a 7-connected graph with |G|>-15, M be a perfect matching. If the order of fragment in G is at least 3, M contains at least two contractible edges.