The Decycling Number Of Several Types Of Graphs

The problem of destroying all cycles in a graph by deleting a set of vertices originated from applications in combinatorial circuit design, deadlock prevention in operating systems, etc. Decycling problem is important in graph theory, which is closely related to the size of the largest induced forest, connectivity, the size of independent set, etc. Exploring decycling number contributes to a better understanding of the structure and properties of graphs. In this paper, we will discuss the decycling number of several types of simple graphs.Given a graph G=(V(G), E(G)), if S (?) V(G) and G-S is acyclic, then S is said to be a decycling set of G. A decycling set with the minimum cardinality is said to be a minimum decycling set. The size of a minimum decycling set of G is called the decycling number of G, denoted by φ(G), i.e.φ(G)=min{|S|:S c V(G) is a decycling set of G}.In this paper, a structural description of planar triangular graphs with the decycling number of2or3is presented and it’s based on connectivity obtained by Bau and Beineke [1]. Let S be a decycling set of G:G-S is a path if φ(G)=2; every component of G-S is one of the structures6,7and8if φ(G)=3. New bounds on the decycling number of graphs G with the maximum degree less than or equal4are also presented. It satisfies φ(G)≤|V(G)|+1/2. Particularly, if G is not4-regular graph, it satisfies φ(G)≤|V(G)|/2. It implies that the conjecture about planar graphs posed by Albertson and Berman [2] in1976is right when the maximum degree of G (not necessarily planar) is less than or equal4except4-regular or G is4-regular graph with even order. In addition, we also obtain that the decycling number of Halin graph G (G=T∪C, where T is a characteristic tree and C is an adjacent cycle) satisfies φ(G)≤[|V(C)|/2, and cubic Halin graph can make equality hold. It confirms that the conjecture posed by Albertson and Berman [2] is right for every Halin graph.