| Graph theory can be traced back to more than two hundred years ago,after entering the 1970s,the development of graph theory ushered in a golden age,e-specially the emergence of large electronic computers,it is possible to solve a lot of problems.There has been an explosive development in graph theory and appli-cations of almost all discipline,such as physical chemistry、operational research、computer science、electronics、information and communication、social science and economic management.Domination theory is an important part of graph theory,and the introduction of domination functions greatly enriches the research contents of graph domination theory.Signed domination function is a special kind of domination function.There have been many results about the signed domination numbers.For general graphs,it is di cult to determine their signed domination numbers.But for a special graph,due to its structural characteristics,it is easy to construct its minimum signed domination function,and further determine its signed domination number.On the basis of signed domination numbers of P3×Pnand P3×Cnstudied by B.G.Xu,this paper will study signed domination functions of P4×Pnand P4×Cn,and determine their signed domination numbers.Firstly,the n of P4×Pnis classified according to the remainder of module 5.An upper bound for the signed domination number of P4×Pnis obtained by constructing a signed domination function f with smaller weights.Mathematical induction is applied to prove that f is the minimum signed domination function of P4×Pn,and then the sign domination number of P4×Pnis determined.Secondly,the n of P4×Cnis classified according to the remainder of module 5.An upper bound for the signed domination number of P4×Cnis obtained by constructing a signed domination function f0with smaller weights.Mathematical induction and the signed domination number of P4×Pnare applied to prove that f0is the minimum signed domination number of P4×Cn.Then the signed domination number of P4×Cnis determined. |
PDF Full Text Request