Feedback number of (n, k)-star graphs

Abstract

Given a graph G = (V,E), the minimum feedback vertex set F is a subset of vertices of minimum size whose removal induces an acyclic subgraph. This paper investigates the feedback vertex set of the (n, k)-star graphs S_n,k. Let f(S_n,k) denote the minimum cardinality over all feedback vertex sets of the (n, k)-star graphs S_n,k. This paper gives the exact feedback number of the (n, 2)-star graph and the (n, 3)-star graph, that is, f(S_n,2) = n(n-3), n ≥ 4 and f(S_n,3) = n(n - 1)(n - 4), n ≥ 6.