点击次数：

论文类型：期刊论文

发表时间：2010-01-01

发表刊物：COMPUTERS & MATHEMATICS WITH APPLICATIONS

收录刊物：SCIE、EI、Scopus

卷号：59

期号：2

页面范围：716-723

ISSN号：0898-1221

关键字：Feedback vertex set; Feedback number; de Bruijn 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. Let f (d, n) denote the minimum cardinality over all feedback vertex sets of the de Bruijn digraph B(d, n). This paper proves that for any integers d >= 2 and n >= 2
   f(d, n) = {1/n Sigma(i|n) di phi (n/i) for 2 <= n <= 4; d(n)/n + o(nd(n-4)) for n >= 5,
   where i I n means i divides n, and co(i) is the Euler totient function. (C) 2009 Published by Elsevier Ltd