Research On The Upper And Lower Bound Of Feedback Numbers Of Several Graphs

The problem of feedback number stems from the practical problems, it has been widely used in many fields, such as the prevention of computer deadlock, avoiding broadcast storms in Internet, testing the electronic circuit and other issues. It has been proved that feedback number problem is NP-hard problem and the study of it has helped to solve other NP-hard problems.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.We hope that the feedback vertex set is the smaller the better.The number of the smallest feedback vertex set is the feedback number of G.Crossed cubes CQn and Locally twisted cubes LTQn are two important modifications of the Hypercubes Qn,they retain some important properties, such as when the dimension is n, there are2" vertexs, n2n-1edges and they are all n regular graphs,even more,they have better properties than the hypercubes, such as under the same dimension,their diameters are the half of the hypercubes’. For the characteristics of such quality, the study of the modified hypercube is significant.In this paper, we study the feedback number of Crossed cubes, by constructing the very small decycling sub-graph of G[V(CQn)\F], we get the upper bound of the feedback number. Then we prove that the feedback number of Crossed cubes is as follows:According to the difference of the last byte of the Locally twisted cubes’vertexs, we put the set of vertices into two disjoint sets, then construc the very small decycling sub-graph of LTQn, then we prove that the feedback number of Locally twisted cubes is as follows:The Flower Snark and its related graphs are3regular graphs,they have the same definition. But when the dimension n is odd and n≥5, we call the graph as Flower Snark, other case the graph is called the related graphs of Flower Snark. With the help of computer and mathematical proof, we get an accurate value of the feedback number of the Flower Snark:...