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

作     者：高红 黄佳欢 刘仁邦 杨元生 GAO Hong;HUANG Jiahuan;LIU Renbang;YANG Yuansheng

作者机构：大连海事大学理学院辽宁大连116026 大连理工大学计算机科学与技术学院辽宁大连116024 

出 版 物：《大连理工大学学报》 (Journal of Dalian University of Technology)

年 卷 期：2022年第62卷第3期

页      面：309-320页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

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

主　　题：罗马{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}-控制数的下界.