点击次数：

论文类型：期刊论文

发表时间：2014-11-01

发表刊物：UTILITAS MATHEMATICA

收录刊物：SCIE

卷号：95

页面范围：51-63

ISSN号：0315-3681

关键字：Feedback vertex set; Feedback number; (n, k)-star graph; Acyclic subgraph

摘要：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.