Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2011-06-01

Journal: TAIWANESE JOURNAL OF MATHEMATICS

Included Journals: SCIE、Scopus

Volume: 15

Issue: 3

Page Number: 1101-1113

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