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

作者：高红; 黄佳欢; 尹亚男; 杨元生

来源：同济大学学报(自然科学版), 2021, 49(05): 751-758.

• 图的控制
• 意大利控制数
• Petersen图

在图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)意大利控制数的精确值。

• 单位
  大连理工大学; 大连海事大学