广义Petersen图P(n,1)和P(n,2)的意大利控制数

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

摘要:

在图G=（V， E）中，f为从顶点集合V到｛0，1，2｝的映射，如果满足所有 f（v）=0的顶点v其邻域中至少有一个被赋值为2的顶点或者至少有两个被赋值为1的顶点，则 f 称为图G的意大利控制函数。图G中所有顶点的函数值之和为f 的权重。权重的最小值为图G的意大利控制数。确定图的意大利控制数是NP （non?deterministic polynomial） 困难的。通过构造可递推的意大利控制函数，计算出广义Petersen图P（n，1）和P（n，2）意大利控制数的上界。利用袋装法和控制代价函数法分别证明出P（n，1）和P（n，2）意大利控制数的下界。最终确定了P（n，1）和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.