Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2012-06-30

Journal: INFORMATION PROCESSING LETTERS

Included Journals: EI、SCIE

Volume: 112

Issue: 12

Page Number: 473-478

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