Research On The Efficient Domination Of Several Classes Of Graphs

All graphs considered in this thesis are undirected and simple.Generally,we use G?(V,E)to represent a graph,where V?V(G)and E? E(G)represent vertex and edge sets of graph G respectively.The domination theory of graphs is a very important research branch in graph theory.A subset D C V(G)is a dominating set of graph G,if each vertex not in D is adjacent to at least one vertex in D.The domination number of graph G,denoted by ?(G),is the cardinality of the smallest dominating set.The bondage number of graph G,denoted by b(G),is the minimum number of edges whose removal results in a graph with larger domination number.A subset Dt(?)V(G)is a total dominating set of graph G without isolated vertices,if each vertex x?Vis adjacent to at least one vertex in Dt.The domination theory f graphs has many important applications in practice,such as location problems.ccording to the actual application,many dominations in variety are derived.Total omination is one of the more important ones.In this thesis,we mainly introduce the efficient dominating set of the(n,k)-star graphs and(n,k)-pancake graphs.The(n,k)-staa and(n,k)-pancake graphs are two important families of interconnection networks that generalize the star graphs and the pancake graphs.We determine all effcient dominating sets for(n,k)-star graphsa nd(n,k)-pancake graphs.Moreover,the bondage numbers of those two graphs are etermined.For the burnt pancake graphs,we give the partial effcient dominating sets and a lower bound of the total bondage number.The full thesis is divided into 4 chapters.In the first chapter,we introduce the development history of graph theory and he research background and progress of the domination theory,and we present the related definitions of the efficient dominating set of graphs and preliminary knowledge.In the second chapter,we mainly study the effcient dominating set and bondage number of(n,k)-star graphs and(n,k)-pancake graphs,and give a very detailed roof for the corresponding results.This chapter is the core content of this thesis.In the third chapter,a partial effcient total dominating set is given for the burnt ancake graphs,and a lower bound of the total bondage number is derived from the relationship between the total bondage number and the effcient total dominating set.Tn the fourth chapter,we summarize the work in this thesis and the main results,e present some problems for future research work.