圈与圈克罗内克乘积图罗马{3}-控制

作者：高红^*; 黄佳欢; 刘仁邦; 杨元生

来源：大连理工大学学报, 2022, 62(03): 309-320.

• 罗马{3}-控制数
• 圈
• 克罗内克乘积

给定图G=(V,E),f是从顶点集合V到{0,1,2,3}的函数，如果对于所有f(v)=0的顶点v都有其开邻域中顶点的函数值之和大于等于3,并且对于所有f(v)=1的顶点v都有其开邻域中顶点的函数值之和大于等于2,那么f称为图G的罗马{3}-控制函数(R{3}-DF).f的权重w(f)是图G中所有顶点的函数值之和，权重的最小值称为图G的罗马{3}-控制数.确定图罗马{3}-控制数是NP困难问题.给出了圈与圈克罗内克乘积图罗马{3}-控制数的上界和下界.通过构造可递推的罗马{3}-控制函数，得到了圈与圈克罗内克乘积图的罗马{3}-控制数的上界.结合前人的成果得到了圈与圈克罗内克乘积图罗马{3}-控制数的下界.

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