广义Petersen图P(n,1)和P(n,2)的意大利控制数
作者:
作者单位:

1.大连海事大学 理学院,辽宁 大连 116026;2.大连理工大学 计算机科学与技术学院,辽宁 大连 116024

作者简介:

高红(1976—),女,副教授,工学博士,主要研究方向为图的控制理论、机器学习算法等。 E-mail: gaohong@dlmu.edu.cn

通讯作者:

中图分类号:

O157.5

基金项目:

国家自然科学基金(60271079)


Italian Domination Number of Generalized Petersen Graph P(n,1) and P(n,2)
Author:
Affiliation:

1.College of Science, Dalian Maritime University, Dalian 116026, China;2.School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    在图G=(VE)中,f为从顶点集合V到{0,1,2}的映射,如果满足所有 fv)=0的顶点v其邻域中至少有一个被赋值为2的顶点或者至少有两个被赋值为1的顶点,则 f 称为图G的意大利控制函数。图G中所有顶点的函数值之和为f 的权重。权重的最小值为图G的意大利控制数。确定图的意大利控制数是NP (non?deterministic polynomial) 困难的。通过构造可递推的意大利控制函数,计算出广义Petersen图Pn,1)和Pn,2)意大利控制数的上界。利用袋装法和控制代价函数法分别证明出Pn,1)和Pn,2)意大利控制数的下界。最终确定了Pn,1)和Pn,2)意大利控制数的精确值。

    Abstract:

    In a graph G = (VE), let f be a mapping from vertex and set V to {0, 1, 2}. If every vertex v such that fv)=0 is adjacent to at least one vertex assigned 2 under f or adjacent to at least two vertices assigned 1 under f, then f is called an Italian domination function of G. The sum of f v) all over G is the weight of f. The minimum weight is the Italian domination number of G. To determine the Italian domination number of a graph is NP-complete. The upper bounds on Italian domination numbers of Pn,1) and Pn,2) are calculated by constructing recursive Italian dominating functions. The lower bounds on Italian domination numbers of Pn,1) and Pn,2) are proved using the bagging method and the dominating cost function method respectively. Therefore, the Italian domination numbers of Pn,1) and Pn,2) are determined.

    参考文献
    相似文献
    引证文献
引用本文

高红,黄佳欢,尹亚男,杨元生.广义Petersen图P(n,1)和P(n,2)的意大利控制数[J].同济大学学报(自然科学版),2021,49(5):751~758

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-10-23
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2021-05-24
  • 出版日期: