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

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2024-01-16

-->

高红,黄佳欢,刘仁邦,杨元生.圈与圈克罗内克乘积图罗马{3}-控制[J].,2022,62(3):309-320

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

Roman {3}-domination in Kronecker product of cycles

DOI：10.7511/dllgxb202203011

中文关键词:罗马{3}-控制数圈克罗内克乘积

英文关键词:Roman {3}-domination number cycle Kronecker product

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

作者	单位
高红,黄佳欢,刘仁邦,杨元生

摘要点击次数:126

全文下载次数:135

中文摘要:

给定图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}-控制数的下界．

英文摘要:

Given a graph G=(V, E), f is a function from vertex set V to {0, 1, 2, 3}. If for every vertex v withf(v)=0, the sum of the function values of the vertices in the open neighborhood ofv is greater or equal to 3, and for every vertex vwith f(v)=1, the sum of the function values of the vertices in the open neighborhood of v is greater or equal to 2, then fis called a Roman {3}-dominating function (R{3}-DF) of graph G. The weight off, w(f), is the sum of the function values of the vertices all over graph G. The minimum of w(f) is the Roman {3}-domination number of graph G. To determine the Roman {3}-domination number of a graph is an NP complete problem. The upper and lower bounds on the Roman {3} domination numbers of Kronecker product of cycles are presented. The upper bounds are obtained by constructing recursive Roman {3}-dominating functions. The lower bounds are determined based on the result given by others.

查看全文查看/发表评论下载PDF阅读器

关闭

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

本站小编 Free考研考试/2024-01-16

相关话题/

领限时大额优惠券,享本站正版考研考试资料!