Feedback Number Of Generalized Kautz Digraphs GK(2,n) And Alternating Group Graphs AG_n

A subset of vertices (resp. arcs) of a graph G =(V,E) is called a feedback vertex set of G if its removal results in an acyclic subgraph. Let f_v(G) (resp.f_a(G)) denote the minimum cardinality over all feedback vertices (resp. arcs) sets of the graph G.The minimum feedback vertex set problem has received intense research interest for its applications in various fields. For example, installation of wavelength translators into the fiber optic network; avoiding broadcasting storms in network transmission; avoiding deadlock in computer operating systems, etc. All of these problems could be abstracted and transformed into finding the minimum feedback vertex set of a given graph.For its theoretical and practical value, this paper explores the feedback number of generalized Kautz digraphs GK(2,n) and alternating group graphs AG_n with the help of related feedback number algorithm.Regarding to the generalized Kautz digraphs GK(2,n), this paper divides V(GK(2,n)) into six subsets. Bases on the subdivision, this paper provides and proves a upper bound of the feedback number of GK(2,n), that is,Regarding to the alternating group graphs AG_n,this paper defines n -1 subsets of V(AG_n) and proves that the union of these subsets forms an acyclic subgraph on AG_n.Thus, this paper gives and proves a upper bound of the feedback number of AG_n for n≥5, that is,...