On Domination-Stability Of Graphs

Though a young discipline, graph theory has been developing rapidly during the recent decades, because of its wide applications in various fields. By the diversity of applications to both theoretic and applied problems, domination has become one of the major areas of graph theory after 30 years' development. Such a close interrelation between graph theory and reality motivates us to investigate the domination-stability of graphs with respect to edge alteration, i.e., we consider the effect of edge operations on the domination number. The reason to choose such a dynamic angle is that, graphs are good models of many practical problems, but sometimes they have to be changed to fit the change of reality; as a result, we must pay attention to the change of graph invariants and properties under graph alterations. Specifically, in this dissertation we mainly focus on three parameters - bondage number, reinforcement number and domination contraction number, which reveal the domination-stability of graphs with respect to three fundamental edge operations - deletion, addition and contraction.For the bondage number b(G), we first obtain a series of results for graphs with small crossing number, which contain the known upper bounds for planar graphs. The most important two of these results are b(G) ≤ min{8, △(G) + 2} if cr(G) ≤ 3, andThen we consider de Bruijn digraph B(d,n) and Kautz digraph K(d,n), which, as topo-logical architecture of interconnection networks, have many attractive features superior to the hypercube, and thus become good candidates for the next generation of parallel system architectures after the hypercube networks. We prove that the bondage numbers of de Bruijn and Kautz digraphs areWe also determine the total bondage number b_t(G), which is a variation of bondage number with respect to total domination, of de Bruijn and Kautz digraphs:b_t(B(d,n)) = d - 1 for d ≥ 2, and b_t(K(d,n)) = d for d ≥ 1. Finally we obtain that bondage number of a k-regular vertex-transitive graph G which has efficient dominating sets isif G is undirected; if G is directed.Applying this result we determine the bondage number of some popular networks, including double loop networks, torus and cube-connected cycles.For the reinforcement number r(G), we introduce this number for digraphs and obtain many results similar to those for undirected graphs. We also investigate the relationship between the reinforcement number of undirected graphs and this number of digraphs. Then we consider two questions proposed in a survey paper of reinforcement number: we give a partial characterization of equalities in a known upper bound of r(G), and present new lower and upper bounds for a k-regular graph G: otherwise,where γ = γ(G) ≥ 2 and (?) = γ (k + 1) - n(G). Lastly we determined this number for de Bruijn and Kautz digraphs:Motivated by the recent research on (total) domination subdivision number, we introduce the concept of (total) domination contraction number and presents its application. We prove that for any graph the (total) domination contraction number must be 0, 1, 2 or 3, and characterize the four classes of graphs with these four (total) domination contraction numbers.In the end, we conclude our research and give some immature results on the conjectures for bondage number of planar graphs. We also propose many problems that are worthy of further in-depth consideration.