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

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

来源：大连理工大学学报, 2023, 63(05): 544-550.

• 3-彩虹控制
• 全局3-彩虹控制
• 补图
• 刻画

对于任意正整数k,图G的k-彩虹控制函数f定义为从图G的顶点集V到集合{1,2,…,k}的幂集的映射，使得任意满足f(u)=?的顶点u,都有■,其中N(u)是u的开邻域.图G的k-彩虹控制函数f的权为■.如果f是图G及其补图的k-彩虹控制函数，则称f是图G的全局k-彩虹控制函数.图G的k-彩虹控制数γrk(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等的结果.

• 单位
  菏泽学院; 东华理工大学; 厦门理工学院