| Abstract: | Let  and  denote the minimum size of a decycling set and maximum genus of a graph G, respectively. For a connected cubic graph G of order n, it is shown that  . Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set S in a k‐regular graph G is  , where c and  are the number of components of  and the number of edges in  , respectively. Therefore, S is minimum if and only if  is minimum. As an application, this leads to a lower bound  for  of a k‐regular graph G. In many cases this bound may be sharp. |
