Research On Feedback Numbers Of Kautz Graph K(d,n) And Knodel Graph W(4,n)

If we get an acyclic graph after remove a subset of G from G= (V,E),we call the subset F as the feedback vertex set. The number of the smallest feedback vertex set is the feedback number of G. the feedback number is a important parameter of interconnection network topology.People pay attention to the problem of minimum feedback point set problem, which is widely used in many fields.For example, the wavelength change device in optical fiber network installation problems of broadcast storm in the network transmission process to avoid problems proof graph of the minimum feedback vertex set problem can be by a computer operating system to avoid deadlock problem is transformed to.In fact, because the structure of the interconnection network can be abstracted as a graph,the graph theory plays an irreplaceable role in the design and analysis of interconnection networks. Through the study of some special interconnection network topology, we will pave the way for a new generation of computer systems.The author mainly uses computer algorithms and mathematical induction methods combine to give an estimate of the number of feedback following two graphs sector:First study the feedback number f(d,n) for Kautz graph K(d,n), when the asymptotic formula of n≥8 improveSecondly study feedback number f(n) for Knodel graph W4,n, This paper presents a new method of non circle map for W4,n, Prove that for any integer n greater than or equal to 18, the feedback numbers of W4,n is:...