Research on Decycling Numbers and Related Problems of Graphs

Author:Yang Chao

Supervisor:Hold the post of Han


Degree Year:2017





Decycling number is one of the most important problems in graph theory,it results from computer science,and has a strong theoretical significance and practical significance.Now,decycling number is widely applied in production and practice,and will become an important field where many researchers have concerned with.Up to now,one have obtained many rich results,and these results are still under improvement.In this paper,we investigate on the decycling number and some related problems of graphs.We have constructed our works in eight chapters.In Chapter 1,firstly,notations and terminologies of graph theory are intro-duced and defined.Secondly,the main results in this thesis are listed.In Chapter 2,we give some notations of decycling number and introduce some current states for the decycling number of planar graph,cubic graph,hypercubic,and cartesian products graphs.In Chapter 3,from the view of independent set and covering set of graphs,we obtain two formulae for the decycling number of graphs:(1)(?)(G)= n-T mrax{α(G-E(T))};(2)(?)(G)= T min {β(G-E(T))},where T is a spanning tree of G,α(G-E(T))and β(G-E(T))denote the independence number and the covering number of the co-tree G-E(T),respec-tively.To date,there is relatively little discussion on the the decycling number of dense graphs,while the above two formulae can determine the decycling number of some dense graphs.In Chapter 4,we get a new formula for the decycling number of k-regular graphs,where c(G)= ‖ G ‖-| G | + 1,m(S)= c + |E(S)|-1,c and |E(S)| are the number of components of G-S and the number of edges of induced subgraph G[S].Based on the above formula,we completely solve the decycling number of 3-regular graphs,and furthermore,we also obtain a vertex partition,vertex arboricity and adjacent vertex distinguishing total chromatic number of 3-regular graphs.In Chapter 5,we investigate a class of special nearly k-regular Halin graph and get an exact value for the decycling number of three types of k-regular Halin graphs.In Chapter 6,we study a type of plane triangulation graph GnK4 and give its decycling number for n = 1,2,3,4.In Chapter 7,we weaken the condition for the decycling graphs and present a new notation that eliminating the shortest cycle of graphs.We prove that(?)where △s(G)is the number of a minimum vertex set which removed can destroy all shortest cycles of G.In Chapter 8,we give some further researching problems of decycling number.