Feedback vertex set of generalized de Bruijn digraphs GB(d,n)

Abstract

A subset of vertices of a graph G is called a feedback vertex set of G if its removal results in an acyclic subgraph. In this paper, we consider the feedback vertex set of generalized de Bruijn digraphs GB(d,n). Let f(d, n) denote the minimum cardinality over all feedback vertex sets of the Generalized de Bruijn digraph GB(d,n), we obtain the upper bound of f(d, n) as follows {4+7m + [5t=3/8 + [3t/4] - [5t/8] - [t+1/2], m = [n/32],n ≅ t (mod 32), for d = 2, f(d,n) ≤4+6m + [7t/9] - [t+1/3, m= [n/18], n ≅ t (mod 18), for d =3, 2 + t + d(2d-3)m+[(d+1)t+d-1/d²] - [t/d], m=[n/d(2d+3)], n ≅ t (mod (d(2d+3))), for d≥ 4.