Research On Feedback Numbers Of Some Important Interconnection Network Topological Structure Graphs

The problem of feedback numbers of graphs originated in a practical application. Some applications of the problem are in operating systems to resource allocation mechanisms that prevent deadlocks, in attacking networks to seek for the mimimum attack vertex sets, et al., which are equivalent to determining the miminum feedback vertex set of a graph G.The minimum feedback vertex set problem is known to be NP-hard for general graphs. Each progress of determining the minimum feedback vertex set of a graph G is very difficult. Because of its difficulty, only a few graphs obtain the feedback numbers, and the bound of feedback number of graphs have not been obtained much.This thesis studies the feedback number of some important graphs which are closely related to interconnection network topological structure design method (Cartesian Product Methods, Line Graphical Methods and Cayley Methods). We give the feedback number of Flower Snark and its related graphs Jn, Knodel graph of W?,n and Circulant graph Cn(1,k), respectively. We also obtain the tight upper and lower bound on the feedback number of Augmented Cube, an upper bound on the feedback number of Locally Twisted Cube, respectively. Mealwhile, we give an upper bound on the feedback number of Kautz digraph K(d,n). The main results are as follows.(1) The thesis studies the feedback number of Flower Snark graph and its related graphs Jn,W3n, W4,n and Circulant graph Cn(1,k). By using loop structure of Flower Snark graph, W3,n,W4,n and Circulant graph, we construct the corresponding loop structure of acyclic subgraph of vertex sets, respectively. On the basis of these vertex sets, getting the results are as follows.? It obtains the feedback number of Flower Snark and its related graphs f(Jn)=n+1;It obtains the feedback number of W3n f(W3,n)=(?)It obtains the feedback number of W4,n f(W4,n)=(?)? It obtains the feedback number of Circulant graph Cn (1, k), where even n?5k+1+2(((k+1)/2)mod3),3?odd k<n/2 f(Cn(1,k))=?(n+1)/3?.(2) The thesis studies the feedback number of two variant of hypercubes network Augmented Cube and Locally Twisted Cube. By using the recurrence structure and the properties of edge set of two variant of hypercubes network Augmented Cube and Locally Twisted Cube, we construct the recurrence structure of acyclic subgraph of vertex set function, respectively. On the basis of these vertex set function, getting the results are as follows:? It gives a tight upper and lower bound on the feedback number of Augmented Cube AQn. 2n-3×2n-3?f(AQn)?2n-(2n-2+2((n+1)/2?(n-1)/2?);? It gives an upper bound on the feedback number of Locally Twisted Cube LTQn. f(LTQn)?2n-1.(3) The thesis also studies the feedback number of Kautz digraph K(d,n). We obtain a much smaller feedback vertex sets. We give new vertex short expressions of feedback vertex set of Kautz digraph K(d,n). On the basis of the new vertex short expressions, we obtain a much smaller feedback vertex set. We give an upper bound of the feedback number of K(d, n). and have reduced asymptotic estimation from O(dn-4) to O(d2)...