Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2009-07-01

Journal: UTILITAS MATHEMATICA

Included Journals: Scopus、SCIE

Volume: 79

Page Number: 107-124

ISSN: 0315-3681

Key Words: Feedback vertex set; Feedback number; Generalized 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. In this paper, we consider the feedback vertex set of generalized de Bruijn digraphs GB(d, n). Let f(d, n) denote the minimum cardinality over all feedback vertex sets of the Generalized de Bruijn digraph GB (d, n), we obtain the upper bound of f (d, n) as follows
   [GRAPHICS]