Study On The Domination Of Trees And The Bondage Number Of The Strong Product Of Graphs

The domination number is one of basic invariants of graphs. It is also a parameter to reflect the performance of networks. The bondage number of a graph G is the cardinality of a minimum set of edges whose removal from G results in a graph with a domination number greater than that of G. It can measure the vulnerability of a communication network under link failure. However, the problems of determining the domination and bondage numbers of a general graph were proved to be NP-complete and NP-hard, respectively. Many authors devote themselves to the research on the property and construction of minimum dominating sets and bondage edge sets of a graph, and the calculation of the exact values and bounds of some special kinds of graphs. Generally speaking, it is more difficult to calculate the bondage number than the domination number of a graph.The main contents of this thesis include the domination of trees and the bondage number of strong product of graphs. And the study on the former can offer some help for us to calculate the latter.This thesis contains six chapters. In Chapter 1, we first introduce some basic concepts and notations. Then we introduce the background and the development of the construction and characterization of trees and the bondage number of strong product of graphs, respectively. At last, we outline the main results obtained in the following chapters.In Chapter 2, all the vertices of a graph are partitioned into three kinds — — universal vertices, idle vertices and alterable vertices according to the relation between them and the minimum domination sets. (A vertex of a graph G is called universal if it belongs to every minimum dominating set of G, idle if it does not belong to any minimum dominating set of G, and alterable if it is neither universal nor idle.) Also, we define nine operations of graphs and give the constructions of trees only containing alterable, non-universal and non-alterable vertices by these graph operations, respectively.In Chapter 3, we will give a sufficient condition and a necessary and sufficient condition of a tree having bondage number 2:if a tree T has order at least three and all the vertices of it are alterable, then T has bondage number 2; a nontrivial tree T has bondage number 2 if and only if the set composed of all the γ-isolable vertices of T is a maximum 2-packing of T, (A vertex of a graph is called γ-isolable if its removal from the graph decreases the domination number by 1). In addition, we get some properties of the minimum dominating sets of the strong product of a graph and a tree.In Chapter 4, we obtain the exact value of the bondage number of the strong product of two paths. That is, for any two positive integers m ≥ 2 and n ≥ 2, b(Pm(?)Pn)= 7-r(m)-r(n) if (r(m),r(n))= (1,1) or (3,3),6-r(m)-r(n) otherwise, where r(t) is a function of positive integer t, defined as r(t) = 1 if t≡1 (mod 3), r(t)=2 if t≡2 (mod 3), and r(t)=3 if t≡0 (mod 3).In Chapter 5, we obtain the exact value of the bondage number of the strong product of a complete graph and a path. That is, for any two integers m≥1 and n≥2, b(Km(?)Pn)=[m/2] if n≡0 (mod 3); m if n≡2 (mod 3); [3m/2] if n≡1 (mod 3). Furthermore, we determine the exact value of the bondage number of the strong product of a complete graph and a special starlike tree.In Chapter 6, we give some upper bounds of the bondage number of the strong product of a nonempty graph and a tree under different conditions. Moreover, we show that all the upper bounds we get are sharp by citing the result we obtained in Chapter 5.