Research On Two Kinds Of Domination Numbers Of Cartesian Product Of Cycles

Domination on graphs is one of hot fields in graph theory with great theoretical significance and practical application value.It is widely used in computer algorithm design,group decision making,communication network design and social network analysis.In the big data age,the networks structures used for data analysis are complicated,but their topologies have certain regularities,such as the topology of the World Wide Web is the same with that of product graphs.Therefore,study domination of large scale graphs has a lot of applications.In this thesis,we study two kinds of domination numbers for the Cartesian product of cycles,one is Italian domination numbers and another is signed mixed domination numbers.According to the characteristics of vertex neighborhood,edge neighborhood and the defi-nition of Italian domination and signed mixed domination,we develop branch and bound con-ditions.Using the branch and bound conditions,computer algorithms are designed to construct recursive Italian domination functions and signed mixed domination functions.These domi-nation functions are right even for large scale Cartesian product of cycles with many vertices.And the upper bounds on Italian domination number and signed mixed domination number can be calculated by the domination functions.These upper bounds are very close to their lower bounds,and the upper bounds are equal to the lower bounds for some graphs,that is,we get the exact values of the Italian domination numbers for some Cartesian product of cycles.