Research On The Domination Number And Topological Indices

Let G =(V,E)be a graph,where V = V(G)is the vertex-set and E = E(G)is the edge-set.G?H is the Cartesian product of any two graphs G and H.A subset D(?)C V(G)is a dominating set of G if every vertex in V(G)\D is adjacent to at least one vertex in D.The minimum cardinality of a dominating set of G is called the domination number of graph G,denoted by ?(G).A function f:V(G)? {0,1,2} is a Roman dominating function(RDF)if for each vertex u with f(u)=0 is adjacent to at least one vertex v with f(v)= 2.The weight of f is given by f(V(G))=?u?V(G)f(u).The Roman domination number ?R(G)is the minimum weight among all RDFs of G.Let k be a positive integer,a set D C V(G)is a distance k-dominating set of G if every vertex not in D is within distance k from some vertex in D.The minimum cardinality of a distance k-dominating set of G is called the distance k-domination number of G,denoted by ?k.The topological index is not a negligible problem already in graph theory.It can be a mathematical parameter which used for studying physicochemical properties of organic compounds.The first Zagreb index(M1)and second Zagreb index(M2)are originate from the research on total ?-election energy of conjugated molecules,which are degree-based topological indices and defined as M1 =?u?VV(G)d2(u)and M2=?uv?E(G)d(u)d(v).The eccentric distance sum is an eccentricity-based index:?d(G)=?v?V(G)?G(v)DG(v),where ?G(v)the eccentricity of v in graph G,is the maximal distance from it to another vertex,and DG(v)is the sum of distance between v and other vertex in V(G).Harary index is a distance-based index,H(G)=1/2?un=11/d(u,v),where d(u,v)is the distance between u and v.This dissertation mainly study Vizing's Conjecture relate to domination number and the relation between(distance k-)domination number and the topological indices men-tioned in the above paragraph.In chapter one,we introduce the terminology and notation in graph theory and the background of our study.Vizing's Conjecture is a famous conjecture on the domination number,which was proposed by Vizing in 1963,namely,?(G?H)?(G)?(H)holds for any graphs G and H.The Vizing-type inequalities are rarely relate to the Roman domination num-ber,one of these inequalities is obtained by Wu[Y.J.Wu,An improvement on Viz-ing's conjecture,Inform.Process.Lett.113(2013)87-88].In chapter two,we prove?R(G?)??(G)?(H)+ 1/2min{?(G),?(H)} for graph nonempty G or H.It improves the inequality obtained by Wu and is better than other similar results in some cases.AutoGraphiX(AGX)computer system is used for finding conjectures in graph theory by applying the variable neighborhood search metaheuristic and data analysis methods.These conjectures mainly in regard to the bounds on the four fundamental operations of two graph invariants and the corresponding extremal graphs.In chapter three,we correct an AutoGraphiX conjecture regarding the domination number and average eccentricity,and present a proof of the revised conjecture.In addition,we establish a sharp upper bound on ?(T)-ecc(T)for an n-vertex tree T.Borovicanin[B.Borovicanin,B.Furtula,On extremal Zagreb indices of trees with given domination number,Appl.Math.Comput.276(2016)208-218]showed the sharp upper bounds on the Zagred indices of the n-vertex trees with domination number ?.Motivated by this result,we show an upper bound for Zagreb indices in terms of distance k-domination number and characterize the extremal trees in chapter four.Meanwhile,a sharp upper bound,in terms of n,k and ?,on distance k-domination number ?k(T)for an n-vertex tree T is derived.And lastly,we obtain an upper bound on Harary index by applying the known relation between Harary index and Zagreb indices,and characterize the extremal trees as well.In chapter five,we determine the trees having the minimal eccentric distance sum among the n-vertex trees with dist,ance k-domination number,and present some sharp bounds for the eccentric distance sum.