Feedback Number of Generalized Kautz Digraphs \(GK(2,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 investigate the feedback vertex set of generalized Kautz digraphs \(GK(2,n)\). Let \(f(2,n)\) denote the minimum cardinality over all feedback vertex sets of the generalized Kautz digraph \(GK(2,n)\). We obtain the upper bound of \(f(2,n)\) as follows:
\[f(2,n) \leq n-(\left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{{n-2}}{3} \right\rfloor + \lfloor \frac{n-8}{9}\rfloor)\].