Hits:

Indexed by:期刊论文

Date of Publication:2014-11-01

Journal:UTILITAS MATHEMATICA

Included Journals:SCIE

Volume:95

Page Number:51-63

ISSN No.:0315-3681

Key Words:Feedback vertex set; Feedback number; (n, k)-star graph; Acyclic subgraph

Abstract:Given a graph G = (V, E), the minimum feedback vertex set F is a subset of vertices of minimum size whose removal induces an acyclic subgraph. This paper investigates the feedback vertex set of the (n, k)-star graphs S-n,S-k. Let f(S-n,S-k) denote the minimum cardinality over all feedback vertex sets of the (n, k)-star graphs S-n,S-k. This paper gives the exact feedback number of the (n,2)-star graph and the (n,3)-star graph, that is, f(S-n,S-2) = n(n-3), N >= 4 and f (S-n,S-3) = n(n-1)(n-4), n >= 6.