Results Of Removable Edges In Cycles Of 3-connected Graphs

The connectivity of graphs is one of the most important properties of graphs.Connec-ted graphs play an important role in practical applications because of its close connec-tion with network model and combinatorial optimization.With the rapid development of computers and internet,this connection is closer than ever before over the past two decades.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 applications.With induction widely used,operations in graphs which are a series of algorithms that reduce the number of vertices or edges in a graph with keeping some property are more useful day by day.In this context,removable edges and contractible edges are used in research.This paper forces on the properties of removable edges in 3-connected graphs,and their distributions in cycles.The following are the main results.In this paper,G is a simple graph.First,we will give a definition.Consider the following operations:(1)Delete e from G,resulting in the graph G-e.(2)lf some end-vertices of e have degree 2 in G-e,then joint them.(3)If multiple edges occur,we use single edges to replace them.The final resultant graph after (1)(2)(3) operations is denoted by G (?) e.For a 3-connected graph G,if G (?) e is still 3-connected,then theedge e is called removable; other-wise,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).The number of all removable edges and unremovable edges of G are denoted respectively by eR(G) and eN(G).For removable edges in cycles of 3-connected graphs,we will give two results as follows:Theorem 3.1 If C is a 7-cycle in 3-connected graph G which is not isomorphic to W8,then: or G conclude a subgraph which is isomorphic to Ws **,where C (?) Ws ** and dG(xi)= dG(yi)=3,i=2,3,4; dG(a)≥4; dG(b)≥4.Theorem 3.2 If C is a 8-cycle in 3-connected graph G which is not isomorphic to W9,then: or G conclude at least one subgraph which is isomorphic to the graph of Ws A,Ws B or Ws C,where C contains inside and dG(xi)=dG(yi)=3,i=2,3,4; dG(a)≥4; dG(b)≥4.(The construction methods about Ws **,Ws A,Ws B and Ws C are in the text)...