The Distribution Of Removable Edges Outside Circles In 3-Connected Graphs

As a very important branch of discrete mathematics,graph theory has a very wide range of applications in chemistry,bioinformatics and social sciences.The connectivity theory of graph is a basic but very important part of graph the-ory.The construction of connected graph is one of the important research topics,which is closely related to network model and combinatorial optimization,so it has important theoretical value and application value.Since 1961,Tutte[33]used the existence of contractible edges and removable edges in 3-connected graphs to give the construction method of connected graphs,people have devoted them-selves to studying the construction of various types of connected graphs.In fact,contractible edges and removable edges not only play an important role in the construction of connected graphs,but also are important tools for recursively proving some properties of graphs.These problems have been concerned and studied by Thomassen etc.For removable edges of 3-connected graphs,Holton[14]etc.first gave the definition of removable edges in a 3-connected graphs.As early as 1969,similar to the result of contractible edges in 3-connected graphs,Barnette[5]etc.proved that every 3-connected graph with order greater than 4 must have removable edges,and gave a recursive construction method of 3-connected graphs.Later,Yin Jianhua[39]defined the concept of removable edges in 4-connected graphs,and proved that there is no removable edge in a 4-connected graph G if and only if G is a bicyclic graph of order 5 or 6.Using this result and the property of 4-contractible edge,a recursive construction method of 4-connected graph is given.His method is much simpler than Slater’s[26].In 2005,Xu Liqiong[37]generalized the concept of removable edges in 3-connected graphs and 4-connected graphs to k-connected graphs in her doctoral dissertation,and proved th at it is different from K6,there must be removable edges in a 5-connected graph.What’s more,she conjectured that,for a k(k>3)-connected graph without removable edges if and only if k is odd,G is isomorphic to Kk+1,and G is isomorphic to Kk+1 or H(k+2)/2 for k being even.Later,the conjecture was verified to be true by Su Jianji[30]etc.So far,the problem of the existence of removable edges in k-connected graphs has been solved satisfactorily.At the same time,the distribution of removable edges in connected graphs has also been widely studied.However,the current research mainly focuses on some special subgraphs,where the special subgraphs mainly refer to some specific cycles and spanning trees.Hamiltonian cycle has always been one of the hot issues in graph theory.Mathematician Thomassen[32]once proposed a classical problem about Hamiltonian graph:whether there is an edge e in a Hamiltonian graph G with minimum degree at least 3,so that G-e and G/e are still Hamiltonian.Through analysis,it is found that if e is an edge on a Hamiltonian cycle,then G/e is still Hamiltonian,but G-e will destroy the Hamiltonian cycle containing edge e.But if e is an edge outside the Hamiltonian cycle,then G-e will not destroy the Hamiltonian cycle without edge e.In view of this finding,it is necessary to explore the distribution of removable edges outside the circle in 3-connected graphs.Inspired by the problem raised by Thomassen,in this paper,we first study the distribution of removable edges outside the circle in 3-connected graphs by using the tools of separation group and maximal fan.Of course,there are requirements for 3-connected graph G.We mainly consider the case when G contains no fan as a subgraph and only one fan as a subgraph,and draw the following conclusions.In this paper,we also construct a 3-connected graph G with two fans as subgraphs,so that there are no removable edges outside the cycle C,which shows that the condition in the theorem 2 is indispensable.The main results of this paper are as follows.Theorem 1.Let G be a 3-connected graph of order at least 6 and C be a cycle in G.If G does not contain a fan as a subgraph,then there are at least two removable edges outside any cycle C.Theorem 2.Let G be a 3-connected graph of order at least 6 and C be a cycle in G.If G contains only one fan as a subgraph,then there is at least one removable edge outside any cycle C.Theorem 3.Let G be a 3-connected graph of order at least 6,and C be a cycle in G.If G contains two fans as subgraphs,then we can construct a 3-connected graph G such that there are no removable edges outside the cycle,which shows that the condition in theorem 2 is essential.