Feedback Number of (n, k)-Star Graphs
Release Time:2019-03-09 Hits:
Indexed by: Journal Article
Date of Publication: 2014-11-01
Journal: UTILITAS MATHEMATICA
Included Journals: SCIE
Volume: 95
Page Number: 51-63
ISSN: 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.