点击次数：

论文类型：期刊论文

发表时间：2014-07-01

发表刊物：ARS COMBINATORIA

收录刊物：SCIE

卷号：116

页面范围：147-160

ISSN号：0381-7032

关键字：Feedback vertex set; Feedback number; Generalized Kautz digraphs; Cycles; Acyclic subgraph

摘要：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 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) <= n - (left perpendicularn/3right perpendicular + left perpendicularn-2/3right perpendicular + left perpendicularn-8/9right perpendicular).