Research On The Stability Of Graphs

Mathematics is a scientific discipline with long history. However, as a filiation of Mathematics, graph theory is very new. With the development of the society and the progress of computer sciences and communication technique, the applications of Mathematics become more and more wider in recent years. Graph theory has made great strides. As a very effective tool of analyzing and solving problems, graph theory has demonstrated its power on management, transportation, military, computer sciences, interconnection networks, chemistry, physics, social sciences and so on. Because the research on graph theory is closely related to applications, and the real world is in a constant state of flux, we must consider the changes of some parameters in graph theory related to the change of graph. In this book, we study the parameters of the stability of graph, mainly on two parameters -bondage number and feedback number.Firstly, we concentrate on the bondage number.We obtain some results for the toroidal graph.If G is a connected toroidal graph, thenWe also obtain some results for graphs with crossing number less than 4, the main result is:Let G be a connected graph. Then the inequality b(G)≤Δ(G) + 2 holds if G satisfies one of the following conditions: Then, we focus on the feedback number. We investigate three famous graphs of interconnection networks:For De Bruijn digraph B(d, n), for any d≥2 and n≥2, the feedback number f(d, n) of B(d, n) is:For De Bruijn undirected graph U B(d,n), for any d≥3 and n≥1, the feedback number f(d, n) of UB(d, n) satisfies the boundary below:For Kautz undirected graph U K(d, n), for any d≥2 and n≥1, the feedback number f(d. n) of U K(d, n) satisfies the boundary below:Finally, we summarize our research, give some premature conjectures, and pose some questions to be further researched.