Research On The Domination Number Of Two Classes Of Graphs

Graph theory is the subject,which studies objects and the relation of objects.Many problems in our real life can be converted to the study of graphs.The domination number of graphs is an important problem and has wide application.Calculating the domination number of graph is a NP-complete problem.It is difficult to give the domination number of the graph or the better boundary of the domination number.There are many domination numbers of complex graphs need to be studied.In this paper,we study the total signed domination number of the Cartesian product of paths Pm?Pn.Pm?Pn is a kind of large-scale graph,and the total signed domination number is difficult,which needs to consider the total neighborhood of vertices and edges.So giving the domination number of the Pm?Pn is difficult.According to the nature and definition of the Pm?Pn,a lower bound is proposed after the mathematical derivation.By branch and bound method and computer programming,we get a upper bound of total signed domination number.According to a series of lemmas,the total signed domination number of the Cartesian product of graphs Pm?Pn is given.In this paper,we also study the Italian domination number of Petersen graph P(n,3).Italian domination number is a new concept of domination number just emerging in recent years.By branch and bound method,the algorithm of calculating the domination number and computer aided,we get a upper bound of Italian domination number.A lower bound is given after the mathematical derivation.We get the exact value of the Italian domination number of Petersen graph P(n,3).