广义Petersen图P(n,1)和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)意大利控制数的精确值.

关键词：图的控制、意大利控制数、Petersen图

所属期刊栏目：49

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金60271079

在线出版日期：2021-05-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：751-758