New bounds on the decycling number of generalized de Bruijn digraphs

A set of vertices of a graph whose removal leaves an acyclic graph is referred as a decycling set, or a feedback vertex set, of the graph. The minimum cardinality of a decycling set of a graph G is referred to as the decycling number of G. For n ≥ d ≥ 2, the generalized de Bruijn digraph GB(d,n) is defined by congruence equations as follows: V (GB(d,n)) = {0, 1, 2,…,n − 1} and A(GB(d,n)) = {(x,y)|y ≡ dx + i(modn), 0 ≤ i < d}. In this paper, we give a systematic method to find a decycling set of GB(d,n) and give a new upper bound that improve the best known results. By counting the number of vertex-disjoint cycles with the idea of constrained necklaces, we obtain new lower bounds on the decycling number of generalized de Bruijn digraphs.