Hits:

Indexed by:期刊论文

Date of Publication:2014-07-01

Journal:ARS COMBINATORIA

Included Journals:SCIE

Volume:116

Page Number:147-160

ISSN No.:0381-7032

Key Words:Feedback vertex set; Feedback number; Generalized Kautz 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 Kautz digraphs GK(2, n). Let f(2, n) denote the minimum cardinality over all feedback vertex sets of the Generalized Kautz digraph GK(2,n), we obtain the upper bound of f(2, n) as follows
   f(2, n) <= n - (left perpendicularn/3right perpendicular + left perpendicularn-2/3right perpendicular + left perpendicularn-8/9right perpendicular).