点击次数：

论文类型：期刊论文

发表时间：2012-06-30

发表刊物：INFORMATION PROCESSING LETTERS

收录刊物：SCIE、EI

卷号：112

期号：12

页面范围：473-478

ISSN号：0020-0190

关键字：Combinatorial problems; Graph theory; Feedback set; Feedback number; (n, k)-star graphs; Cycles; Acyclic subgraph; Networks

摘要：The feedback number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. We use f (n, k) to denote the feedback number of the (n, k)-star graph S-n,S-k and p(n, k) the number of k-permutations of an n-element set. This paper proves that
   p(n, k) - 2(k - 1)!((n)(k - 1)) <= integral (n, k) <= p(n, k) - 2(k - 1)!Sigma(theta)(i=1) ((n - 2i + 1)(k - i)).
   where theta = min{k - 1, n - k + 1}. (c) 2012 Elsevier B.V. All rights reserved,