The Decycling Number And The Maximum Nonseparating Independent Sets Of Two Kinds Of Graphs

This dissertation mainly studies the decycling number of Mobius grids P_m×C_n~?(m=2,3,4,6,7),the decycling number and the maximum nonseparating independent sets of circular graph C(n,2,3).In chapter 1,we introduce the origin and the development of graph theory,the research status and the important achievements of the decycling number and the max-imum nonseparating independent sets firstly.Then some basic difinitions,theorems using in this dissertation and my research findings follow.In chapter 2,we consider three factors which will influence the decycling number,such as degree,independence and the number of components of cograph,and get the lower bound of graph.We take the method of analisis and list to increase the lower bound according to the structural features of graph.We find the corresponding vertexs to prove the equal conditions hold.In the section 1 of chapter 3,we consider two factors which will influence the decycling number,such as independence and the number of components of cograph,and get the lower bound of graph.We take the method of reduction to absurdity to increase the lower bound according to the independence of elimination point and the existence of circular.We find the corresponding vertexs to prove the equal conditions hold.In the section 2 of chapter 3,we prove Z(C(n,2,3))=I when n=6k+1,6k+3,6k+4,6k+6 by list under known the circumstances of the decycling number proved by the section 1 and the independent set of circular graph C(n,2,3).We also prove Z(C(n,2,3))=I-1 when n=6k+2,6k+5 by contradiction.