Hits:

Indexed by:会议论文

Date of Publication:2014-11-15

Included Journals:EI、CPCI-S、Scopus

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.