Feedback Number Of (n, K)-Star Graphs And (n, K)-Arrangement Graphs

For a given simple graph G=(V, E), and F is a subset of V, if the subgraph induced by the vertex set V\F is acyclic, F is a feedback vertex set of graph G; if the cardinality of F is the minimum, F is a minimum feedback vertex set, the cardinality of F is called the feedback number of G. Let f(G) denote the feedback number of G.The feedback number of a graph is one of the important branches of the study of graphic theory. The minimum feedback vertex set problem has very important applications. For example, it can effectively solve the deadlock in the operating system, and it can ensure the communication quality of the network, besides, it can avoid the network transmission of broadcast storms.The problem of finding a minimum feedback vertex set of general graphs proves to be NP-hard. For general graphs, it is difficult to give an accurate algorithm, and we just find the approximate algorithms. Recently, many people focus the studies of feedback number on the special topological graphs, such as hypercubes, folded hypercubes, star graphs, butterfly graphs, line graphs and so on.This paper explores the feedback vertex set of (n,k)-Star graph and (n,k)-Arrangement graph with the help of the combinational methods of computer computing and mathematical reasoning. Based on the property of the (n,k)-Star graphs and (n,k)-Arrangement graphs, we can gain the lower bound of feedback number, f(Sn,k)≥n!(n-k-1)/(n-k+1)!, and f(An,k)≥n!(n-k-1)/(n-k+1)!.For (n,k)-Star graph Sn,k, this paper gives the minimum feedback vertex set if k=2 and k=3. f(Sn,2)=n(n-3),for n≥4. f(Sn,3)=n(n-1)(n-4),for n≥6.For (n,k)-Arrange graph An,k, this paper gives the feedback vertex set if k=2. f(An,2)＝n(n-3)+1,for n≥3.