关于图的全局彩虹控制数

摘要

设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的权为∑x∈V(G)|f(x)|.图G的全局k-彩虹控制函数的最小权称为G的全局k-彩虹控制数.利用分类讨论法和反证法,得到了完全二部图和轮图的全局彩虹控制数的精确值.特别地,纠正了Alqesmah等(2019年)的一个错误结果.此外,还给出了一般图的全局彩虹控制数的上界.