Feedback Number Of Generalized De Bruijn Digraphs GB (d, N)

The feedback number f(G) of graph G is the minimum number of vertices to be removed, which makes the graph acyclic. The feedback number problem has important application to several fields. For example, the problems are used in resource allocation mechanisms that prevent deadlocks in operating systems, in the constraint satisfaction problem andBayesian inference in artificial intelligence, in the study of monopolies in synchronous distributed systems and in converters placement problem in optical networks. Howerve, The feedback number problem is known to be NP-hard for general graphs and got only some approximation algorithm. Determining the feedback number is quite difficult even for some elementary graphs. And the problem has been studied for only few special graphs and digraphs.Generalized de Bruijn network GB(d, n) is a kind of generalization to classic de Bruijn network. Generalized de Bruijn network inherits the good properties of de Bruijn network such as small diameter, high connectivity, and easy routing, and overcomes the restriction on the number of vertices, which expands de Bruijn network to the arbitrary vertex numbers. These properties make generalized de Bruijn network be noticed as a kind of topology structure of network. So, the study of the feedback number of GB(d, n) is very important.In this paper, we design an algorithm with branch and bound, backtr acking and union-find set for structuring the feedback vertex sets of generalized de Bruijn network GB(d, n). Through finding the law of different feedback vertex sets of different d and n, and mathematical proof, we obtain the upper bound of f(d, n) as follows:...