关于图的全局彩虹控制数  

On global rainbow domination number in graphs

作　　者：郝国亮 曾淑婷 谢智红 HAO Guoliang;ZENG Shuting;XIE Zhihong(School of Science,East China University of Technology,Nanchang 330013,China)

机构地区：[1]东华理工大学理学院,江西南昌330013

出　　处：《厦门大学学报（自然科学版）》2023年第4期704-708,共5页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(12061007,11861011);江西省研究生创新专项资金项目(YC2021-S628)。

摘　　要：设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年)的一个错误结果.此外,还给出了一般图的全局彩虹控制数的上界.Let k be an arbitrary positive integer.A k-rainbow dominating function f of a graph G behaves as a mapping from the vertex set V(G)to the power set of{1,2,…,k}such that,for any vertex v with f(v)=■,∪x∈N(v)f(x)={1,2,…,k},where N(v)is the open neighborhood of v in G.If f is a k-rainbow dominating function of G and its complement,then f is called a global k-rainbow dominating function of G.The weight of a global k-rainbow dominating function f of a graph G equals∑x∈V(G)|f(x)|.The global k-rainbow domination number is the minimum weight of a global k-rainbow dominating function of G.By classified discussion and reduction to absurdity,the exact values of global rainbow domination number of complete bipartite graphs and wheels are given.In particular,a wrong result of Alqesmah et al.(2019)is corrected.Furthermore,some upper bounds on the global rainbow domination number of general graphs are derived.

关 键 词：全局彩虹控制数 彩虹控制数 完全二部图 轮图 

分 类 号：O157.5[理学—数学]