Hits:

Indexed by:期刊论文

Date of Publication:2012-06-30

Journal:INFORMATION PROCESSING LETTERS

Included Journals:SCIE、EI

Volume:112

Issue:12

Page Number:473-478

ISSN No.:0020-0190

Key Words:Combinatorial problems; Graph theory; Feedback set; Feedback number; (n, k)-star graphs; Cycles; Acyclic subgraph; Networks

Abstract: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,