On Dominating Functions Of Graphs

Since Euler published the first paper on graph theory, the graph theory has beengradually established and completed and has gained abundant achievements. In graph theory,the domination theory of graphs holds an important position: on one hand, for many practicalproblems, we can build models using graph theory to convert them to calculate thedomination numbers of graphs to solve；On the other hand, the domination theory not onlyhas influences on studying other graph theories, but also deeply affects the development ofother subjects, such as operations research, network theory, game theory, chemistry, biology,and physics, social sciences, linguistics, etc. In the domination theory, determine thedomination number is one of the most fundamental problem, Garey and Johnson proofed in[1],that determine the domination number of any graph is a NP-complete problem. Then,determine the best possible upper and lower bounds of domination numbers has the extremelyvital significance. While, the domination number is usually determined by the dominatingfunction, so we should choose the suitable function if we want to obtain it.we mainly discuss the minus edge dominating function, study the minus edge totaldominating function and the reverse minus edge total dominating function comparatively,finally we discuss the total reverse signed dominating function and the total minus dominatingfunction.We do the following jobs in this paper mainly:In the first chapter of the introduction, we briefly review the background knowledge,application scope and the main research direction of graph theory，especially the dominationtheory of graphs, and introduce the definition、the signs and the operations on graph involvein this paper, at the end of this chapter the main structure of subsequent chapters in this paperare briefly introduced.In chapter two, we discuss the new bounds of the minus edge domination numbers. Itwas introduced by Xu in2007and left some questions in his paper, we study one of thesequestions and establish some new bounds.In chapter three, on the basis of the definitions of minus edge total dominating functionand reverse minus edge total dominating function, we study the bounds of these two kinds ofdomination numbers on the general graph comparatively, we establish the bounds in terms ofthe order, the size, the maximum degree and the minimum degree. Finally, the dominationnumbers of path、circle and wheel on these two domination numbers are given. In chapter four, we study the upper bounds of the total reverse signed domination ongeneral graph, and for special graphsIn chapter five, we put forward the definition of total minus dominating function, whichis a natural development of the total dominating function and the total signed dominatingfunction, thus it makes more significance on domination. On the basis of this, we obtain thebounds of general graphs on the total minus domination numbers.In chapter six, we summarize and review the results which are obtained from chapter twoto chapter five, and the future research direction is also prospected, we hope that it will play arole on the future research.