On The Bounds Of Several Kinds Of Domination Numbers Of Graphs

The domination numbers of graphs play a important role in the sructure of graphs.Recently, there are many research papers on the subject.With the development of society,the models of domination numbers are increasing very rapidly. Although most of domination numbers have good applying background ,the decision problems corresponding to those are NP-complete or NP-hard.Thus it is interesting to investigate the bounds of those.It is useful to design their algorithm.For an arbitrary P of the reals,we define a function P to be a P ?dominating function of a graph G = (V, E) if the sum of its funtion values over any closed neighbourhood is at least l.That is ,for every v € V,f(N[v]) > l.The P ?domination number of a graph is defined to be the infimum of w(f) taken over all P ?dominating functions f.where w(f) = f(V) = f(v).When P = {0,1} we obtain the standard domination number.When P = [0,1],P = {- 1,0,1},P = { - 1,1} we obtain the fractional,minus or signed domination number.At the Eigh-teeneh Southeastern International Conference Combinatorics,Graphy Theory and Computing,S.T.Hedetniemi formally defined {rational domination.Recently,the idea of allowing negative weights was put forward,i.e.minus or signed domination number.In this paper,we survey some results concerning the bounds of signed domination number in an arbitray graph and the strong domination number in a connected graph, Nordhaus-Graddum bounds of the total domination number and the connected domination number.The lower bounds of signed domination number have been studied in [5].In this paper we do further research and obtain some new lower bounds of signed domination number of a graph represented by the new parameter 5*. For a graph G of order n, thenFor a graph G of order n,m = |?G)i,<5* = 5*(G),thenFor a graph G of order n, 6* = 1), thenFor a graph G of order n, 5* - 6*(G),A = A(G),if A = 2r + l(r <= N,r > 1), thenAnd we show that these lower bounds are better than those in [5] if 5* > 3. In the meantime.we give some graphs which attains the bounds.In particular.we obtain the lower bound represented by the new parameter 6* of signed domination number of a bipartite graph. Let G = (X.Y.E) be a bipartite graph of order ,thenThe lower bounds in small-degree graphs have been studied in [7].Based on those,we obtain some results as follows.And we give some graphs which attains the bounds.On the upper bounds of strong domination number, the following conjecture has been put forward by [8].we prove it true for the following case.At the end , motivated by[10],we obtain some Nordhaus-Graddum bounds onthe total domination number and the connected domination number of a graph.