Release Time:2019-03-11  Hits:

Indexed by: Conference Paper

Date of Publication: 2014-11-15

Included Journals: Scopus、CPCI-S、EI

Page Number: 161-165

Key Words: Feedback vertex set; Feedback numbers; Kautz digraphs; Cycles; Acyclic subgraphs.

Abstract: This paper considers the feedback number K (d,n) of Kautz digraphK (d,n) , which is the minimum number of vertices in K (d,n) whose removal results in an acyclic digraph. Xu et al. have determined the exact values of K (d,n) for 1 =.. = 7 and obtained an asymptotic formula f (d,n) = d(n)/n d(n-1)/n-1 + O(nd(n-d)) fo n >= 8 = 8. In this paper, we construct a feedback vertex set of f(d,n) and obtain.. d(n-1)/n + O(d(n/2)) for n >= 8 = 8 asymptotically.