Italian Domination Number of Generalized Petersen Graph P(n,1) and P(n,2)

Abstract:

In a graph G = （V， E）， let f be a mapping from vertex and set V to ｛0， 1， 2｝. If every vertex v such that f（v）=0 is adjacent to at least one vertex assigned 2 under f or adjacent to at least two vertices assigned 1 under f， then f is called an Italian domination function of G. The sum of f （v） all over G is the weight of f. The minimum weight is the Italian domination number of G. To determine the Italian domination number of a graph is NP-complete. The upper bounds on Italian domination numbers of P（n，1） and P（n，2） are calculated by constructing recursive Italian dominating functions. The lower bounds on Italian domination numbers of P（n，1） and P（n，2） are proved using the bagging method and the dominating cost function method respectively. Therefore， the Italian domination numbers of P（n，1） and P（n，2） are determined.

Key words:domination on graphs;Italian domination number;Petersen graph