Removable Edges Of Cycles And Trees In6-connected Graphs

The connectivity is one of the most important properties of graphs, which is also an important research subject. Besides of high theoretical value, Con-nected graphs also play an important role in practical applications because of its close connection with network model and combinatorial optimization. With the rapid development of computers and internet, the practical value of connected graphs is increasingly prominent.It has been a valuable subject to discuss the construction of connected graphs for decades. With induction widely used, operations in graphs which are a series of algorithms that reduce the number of vertices or edges of the graph with keeping some property have increasingly got recognition. In this context, removable edges and contractiblc edges arc defined and widely used in research. The main work of this paper is on removable edges in connected graphs in order to know more about the construction of connected graphs.This paper focuses on the properties of removable edges in6-connected graphs, and their distributions in cycles and spanning trees. The following are the main results of this paper.First, we will give a definition.Let G be a6-connected graph, e=xy is an edge of G. Consider the following operations:(1) Delete e from G, resulting in the graph G—e. (2) If there is a u∈{x, y} which is of degree5, delete u and join each two adjacent vertices of u.(3) If multiple edges occur, we use single edges to replace them which resulting in a simple graph.The final resultant graph after (1)(2)(3) operations is denoted by G Q e. For a6-connected graph G, if G O e is still6-connected, then the edge e is called removable; otherwise, it is called unremovable. The set of all removable edges of G is denoted by ER(G)\whereas the set of all unremovable edges of G is denoted by EN[G).For removable edges in triangles and cycles of6-connected graphs, we give the result asConclusion1:Let G be a6-connected graph with[G]>11and δ(G)>7, then any cycle of G contains at least two removable edges.For removable edges in spanning trees and Hamiltonian cycles of6-connected graphs, we give two results asConclusion2:Let G be a6-connected graph with[G]>11and δ(G)≥7, then any spanning tree of G contains at least two removable edges.Conclusion3:Let G be a6-connected Hamiltonian graph with[G]≥11and δ(G)≥7, then any Hamiltonian cycle of G contains at least three removable edges.