全局3-彩虹控制数与3-彩虹控制数之差为2和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等的结果.

全局3-彩虹控制数等于顶点数的图的刻画

图G的3-彩虹控制函数是指从G的顶点集V到集合{1,2,3}的幂集的映射f,使得任意满足f(v)=■的顶点v均有∪u∈N(ν)={1,2,3}成立,其中N(v)是顶点v的邻域.图G的3-彩虹控制函数f的权为∑ν∈V|f(ν)|.如果f既是图G又是其补图的3-彩虹控制函数,则称f为图G的全局3-彩虹控制函数.图G的全局3-彩虹控制数是指G的全局3-彩虹控制函数的最小权.通过对图的结构分析,利用分类讨论法完全刻画了全局3-彩虹控制数等于顶点数的所有图.