关于图的全局彩虹控制数

作者：郝国亮^*; 曾淑婷; 谢智红

来源：厦门大学学报(自然科学版), 2023, 62(04): 704-708.

• 全局彩虹控制数
• 彩虹控制数
• 完全二部图
• 轮图

设k是任意正整数.图G的k-彩虹控制函数f定义为从G的顶点集V(G)到集合{1,2,…,k}的幂集的映射，使得任意满足f(v)=?的顶点v,均有∪(x∈N(v))f(x)={1,2,…,k}成立，其中N(v)是顶点v的开邻域.若f是图G及其补图的k-彩虹控制函数，则称f是图G的全局k-彩虹控制函数.图G的全局k-彩虹控制函数f的权为■.图G的全局k-彩虹控制函数的最小权称为G的全局k-彩虹控制数.利用分类讨论法和反证法，得到了完全二部图和轮图的全局彩虹控制数的精确值.特别地，纠正了Alqesmah等(2019年)的一个错误结果.此外，还给出了一般图的全局彩虹控制数的上界.

• 单位
  东华理工大学