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

来源：大连理工大学学报杂志2022年第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}-控制数的下界．

关键词：罗马{3}-控制数圈克罗内克乘积

基金资助：国家自然科学基金资助项目(62071079).