Decycling Number And Nonseparating Independence Number Of Graphs

The decycling number and nonseparating independence number of graphs are classical subjects of graph partition theory,which have a close connection.They have a wide range of applications in wireless sensor network,combinatorial circuit design and so on.The thesis mainly study the decycling number and nonseparating independence number of graphs,and their applications.The conclusions are as follows:1.We first give a brief introduction on concepts and terminologies of graph theory.Secondly,we give a complete introduction on the background and results of decycling number and nonseparating independence number.Finally,the main results in the thesis are listed.2.We give a formula for the decycling number in subcubic graphs by using the graph embedding.Further,we present a sufficient and necessary condition for (?) in cubic graphs.3.We consider a certain class of graphs with (?) and establish sufficient conditions for such graphs to be Hamiltonian,Pancyclic and Edge-Hamilton,respectively.4.We give a new formula for the nonseparating independence number,which solves the problem of counting the nonseparating independence number of hypercubes(?).Em-ploying the ideas of counting the decycling number of Cartesian product of two cycles(?),we obtain the nonseparating independence number of(?).Moreover,we find a maximum nonseparating independent set of(?)and(?),respectively.In the end,we describe the relation between maximum genus and nonseparating independence number,and we present the distribution of maximum nonseparating independent sets in subcubic graphs.5.We provide a new formula to estimate the bipartite vertex frustration in terms of maximum cut for graphs.Using the formula and some known results on the maximum cut,we derive several new results on the bipartite vertex frustration of graphs(including dense graphs).Also,we study the bipartite vertex frustration of five classes of composite graphs.In the end,we deal with the decycling number problem of dense graphs...