Hits:

Indexed by:期刊论文

Date of Publication:2010-01-01

Journal:COMPUTERS & MATHEMATICS WITH APPLICATIONS

Included Journals:SCIE、EI、Scopus

Volume:59

Issue:2

Page Number:716-723

ISSN No.: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