Hits:

Indexed by:期刊论文

Date of Publication:2009-07-01

Journal:UTILITAS MATHEMATICA

Included Journals:SCIE、Scopus

Volume:79

Page Number:107-124

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