Research On Two Kinds Of Domination On Generalized Petersen Graphs

Domination on graphs is an important research field in graph theory.It has a lot of ap-plications in real life and other disciplines,such as computer networks and their topologies,communications and transportation.In this paper,we study two kinds of domination number on generalized Petersen graphs,and they are signed mixed domination number of P(n,3)and Italian domination number of P(n,k).First,we get better bounds of signed mixed domination number of P(n,3).According to lower bounds on signed mixed domination number for any graph,we obtain lower bounds on signed mixed domination number of P(n,3).Based on the characteristics of P(n,3),we de-velop effective branch and bound conditions,design computer algorithms,and construct signed mixed domination functions for P(n,3).Upper bounds on signed mixed domination number of P(n,3)can be obtained from signed mixed domination functions.So,we can get better bounds of signed mixed domination number of P(n,3).Second,we get better bounds on Italian domination number of P(n,k)and exact values of Italian domination number of P(n,1)and P(n,2).By constructing recursive Italian dominating functions,upper bounds on Italian domination number of P(n,k)can be calculated.P(n,k)is 3-regular,we can get lower bounds on Italian domination number of P(n,k)according to that of regular graphs.From the characteristics of P(n,1)and P(n,2),lower bounds on Italian domination numbers are derived using mathematical proof.Thus,we obtaining exact values of the Italian domination number of P(n,1)and P(n,2).