DOI: 10.11908/j.issn.0253-374x.20442

作者:

作者单位: 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=（V， E）中，f为从顶点集合V到｛0，1，2｝的映射，如果满足所有 f（v）=0的顶点v其邻域中至少有一个被赋值为2的顶点或者至少有两个被赋值为1的顶点，则 f 称为图G的意大利控制函数。图G中所有顶点的函数值之和为f 的权重。权重的最小值为图G的意大利控制数。确定图的意大利控制数是NP （non?deterministic polynomial） 困难的。通过构造可递推的意大利控制函数，计算出广义Petersen图P（n，1）和P（n，2）意大利控制数的上界。利用袋装法和控制代价函数法分别证明出P（n，1）和P（n，2）意大利控制数的下界。最终确定了P（n，1）和P（n，2）意大利控制数的精确值。



Abstract:In a graph G = （V， E）， let f be a mapping from vertex and set V to ｛0， 1， 2｝. If every vertex v such that f（v）=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 P（n，1） and P（n，2） are calculated by constructing recursive Italian dominating functions. The lower bounds on Italian domination numbers of P（n，1） and P（n，2） are proved using the bagging method and the dominating cost function method respectively. Therefore， the Italian domination numbers of P（n，1） and P（n，2） are determined.





PDF全文下载地址:

点我下载PDF