Hits:

Indexed by:Journal Papers

Date of Publication:2015-07-01

Journal:UTILITAS MATHEMATICA

Included Journals:SCIE

Volume:97

Page Number:183-192

ISSN No.:0315-3681

Key Words:Feedback Vertex Set; Feedback Number; Augmented Cubes; Cycles; Acyclic Subgraph

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