摘要
在图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)意大利控制数的精确值。
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 NPcomplete.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.
作者
高红
黄佳欢
尹亚男
杨元生
GAO Hong;HUANG Jiahuan;YIN Yanan;YANG Yuansheng(College of Science,Dalian Maritime University,Dalian 116026,China;School of Computer Science and Technology,Dalian University of Technology,Dalian 116024,China)
出处
《同济大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2021年第5期751-758,共8页
Journal of Tongji University:Natural Science
基金
国家自然科学基金(60271079)。
