Feedback numbers of de Bruijn digraphs

A subset of vertices of a graph GG is called a feedback vertex set of GG if its removal results in an acyclic subgraph. Let f(d,n)f(d,n) denote the minimum cardinality over all feedback vertex sets of the de Bruijn digraph B(d,n)B(d,n). This paper proves that for any integers d≥2d≥2 and n≥2n≥2f(d,n)={1n∑i∣ndiφ(ni)for 2≤n≤4;dnn+O(ndn−4)for n≥5, where i∣ni∣n means ii divides nn, and φ(i)φ(i) is the Euler totient function.