Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2010-01-01

Journal: COMPUTERS & MATHEMATICS WITH APPLICATIONS

Included Journals: Scopus、EI、SCIE

Volume: 59

Issue: 2

Page Number: 716-723

ISSN: 0898-1221

Key Words: Feedback vertex set; Feedback number; de Bruijn digraphs; Cycles; Acyclic subgraph

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. 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