全局3-彩虹控制数与3-彩虹控制数之差为2和3的树的刻画

Characterization of trees with difference of their global 3-rainbow domination number and 3-rainbow domination number being 2 and 3

对于任意正整数k,图G的k-彩虹控制函数f定义为从图G的顶点集V到集合{1,2,…,k}的幂集的映射,使得任意满足f(u)=的顶点u,都有∪_(x∈N(u))f(x)={1,2,…,k},其中N(u)是u的开邻域.图G的k-彩虹控制函数f的权为∑_(x∈V(G))f(x).如果f是图G及其补图的k-彩虹控制函数,则称f是图G的全局k-彩虹控制函数.图G的k-彩虹控制数γr k(G)和全局k-彩虹控制数γ_(grk)(G)分别指图G的所有k-彩虹控制函数和所有全局k-彩虹控制函数的最小权.2016年,Amjadi等刻画了γ_(gr2)(T)-γ_(r2)(T)=1和γ_(gr2)(T)-γ_(r2)(T)=2成立的所有树T.在此基础上,通过对图的结构分析,利用分类讨论法完全刻画了γ_(gr3)(T)-γ_(r3)(T)=2和γ_(gr3)(T)-γ_(r3)(T)=3成立的所有树T,推广了Amjadi等的结果.

For any positive integer k,k-rainbow dominating function f of graph G is a mapping from the vertex set V to the power set of set{1,2,…,k}such that any vertex u with f(u)=satisfies that∪_(x∈N(u))f(x)={1,2,…,k},where N(u)is the open neighborhood of u.The weight of k-rainbow dominating function f of graph G is∑_(x∈V(G))f(x).If f is a k-rainbow dominating function of graph G and its complement graph,then f is called a global k-rainbow dominating function of graph G.The k-rainbow domination numberγr k(G)and global k-rainbow domination numberγ_(grk)(G)are the minimum weights of k-rainbow dominating function and global k-rainbow dominating function of graph G,respectively.In 2016,Amjadi et al.characterized all trees T for whichγ_(gr2)(T)-γ_(r2)(T)=1 andγ_(gr2)(T)-γ_(r2)(T)=2.Based on above results,by classifying the structure of the graphs into different cases,all trees T for whichγgr3(T)-γ_(r3)(T)=2 andγgr3(T)-γ_(r3)(T)=3 are completely characterized,which generalizes the result of Amjadi et al.