The Bounds On The Bondage Number Of (n-4)-regular Graph

The bondage number was first introduced by Fink et al. in 1990, as an important parameter for measuring the vulnerability of a network. Because the problems of the bondage number is deeply depended on the domination number which plays an important and classic role in graph theory and attracts a lot of consideration among the academic field, the studies on the bondage number are full of value. Meanwhile, determining the exact domination number of general graphs has been proved to be NP-complete by Garey and Johnson [2], so it is very difficult to determine the bondage number. But many excellent works has been done for some graphs with particular structures.As one of the particular graphs, the bondage number of the regular graphs is naturally been paid much consideration. In [10], Fink et al. proved that b(Kn)=?n/2?; b(Kn1,n2,n3,...,nt)= 2t-1,n1=n2=n3=...= nt= 2. In 2012, Hu?Xu [3] proved that b(G)=n-3 for every (n-3)-regular graph. However, no results has been received for k-regular graph with 3?k? n-4. According to this train of thought, this article will focus on the bondage number of (n-4)-regular graph.This article contains four chapters, In Chapter 1, we mainly introduce some basic conceptions, known conclusions and the main results of this article. In Chapter 2, we mainly prove that r(G)= 2 for any (n-4)-regular graph, and the upper bound of the (n-4)-regular graph is (n-4). In Chapter 3, we mainly prove that the lower bound of the (n-4)-regular graph is (n-7). For further research, we proposed some questions at the end of this article.