On the bounds of feedback numbers of (n,k)(n,k)-star graphs

The feedback number of a graph G is the minimum number of vertices whose removal from G   results in an acyclic subgraph. We use f(n,k)f(n,k) to denote the feedback number of the (n,k)(n,k)-star graph Sn,kSn,k and p(n,k)p(n,k) the number of k-permutations of an n-element set. This paper proves thatp(n,k)−2(k−1)!(nk−1)⩽f(n,k)⩽p(n,k)−2(k−1)!∑i=1θ(n−2i+1k−i), where θ=min{k−1,n−k+1}θ=min{k−1,n−k+1}.

► We study the feedback number of a graph. ► We consider the (n,k)(n,k)-star graph, which is a generalization of an n  -star graph. ► We give the lower and the upper bounds of the feedback number for an (n,k)(n,k)-star graph. ► Our result enhances the (n,k)(n,k)-star graph as a network.