点击次数：

论文类型：期刊论文

发表时间：2015-07-01

发表刊物：UTILITAS MATHEMATICA

收录刊物：SCIE

卷号：97

页面范围：183-192

ISSN号：0315-3681

关键字：Feedback Vertex Set; Feedback Number; Augmented Cubes; Cycles; Acyclic Subgraph

摘要：A subset of vertices of a graph G is called a feedback vertex set of G if its removal results in an acyclic subgraph. Use f (n) to denote the minimum cardinality over all feedback vertex sets of the augmented cubes AQ(n). This paper presents an approach to construct an acyclic subgraph of AQ(n) and proves that for any integers n >= 4, the feedback number of AQ(n) is as follows:
   2n - 3 center dot 2n-3 <= f(n) <= 2n - (2n-2 + 2left perpendicular n-1 right perpendicular)