Decycling Number of Circular Graphs
Erling Wei, Yanpei Liu, Zhaoxiang Li · 2009
Abstract The lower and upper bounds on the decycling number of circular graph C(n,k) where k ≤ ⌊ n 2 ⌋ of order n are obtained. The explicit expressions of that of some classes of graphs are presented. Keywords circular graph; decycling number; independent set 1 Introduction: the decycling number of graphs It is well known that the cycle rank of a graph is the minimum number of edges whose removal eliminates all cycles in the graph. The parameter has a simple expression. That is, if G is a graph with p vertices, q edges and k components, then the cycle rank β(G) = q − p + k. It is an important invariant to characterize a graph. The corresponding