Hits:

Indexed by:期刊论文

Date of Publication:2011-06-01

Journal:TAIWANESE JOURNAL OF MATHEMATICS

Included Journals:Scopus、SCIE

Volume:15

Issue:3

Page Number:1101-1113

ISSN No.:1027-5487

Key Words:Graph theory; Feedback vertex set; Feedback number; de Bruijn graphs; Cycles; Scyclic subgraph; Networks

Abstract:The feedback number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. We use f(d, n) to denote the feedback number of the de Bruijn graph UB(d, n). R. Kralovic and P. Ruzicka [Minimum feedback vertex sets in shuffle-based interconnection networks. Information Processing Letters, 86 (4) (2003), 191-196] proved that f (2, n) = [2(n)-2/3]. This paper gives the upper bound on f(d, n) for d >= 3, that is, f (d, n) <= d(n) (1 - (d/1+d)(d-1)) + ((n+d-2)(d-2)).