笛卡尔乘积有向图C_2×C_n与C_3×C_n的3-彩虹控制数

设γ_(rk)(D)是有向图D的k-彩虹控制数且设C_m×C_n是m长有向圈C_m与n长有向圈C_n的笛卡尔乘积有向图.用构造的方法找到了笛卡尔乘积有向图C_2×C_n与C_3×C_n的3-彩虹控制数的上界,并证明了此上界恰好为其下界,即得到了γ_(r3)(C_2×C_n)与γ_(r3)(C_3×C_n)的精确值.

有向图的k-彩虹控制数的界

设γ_(rk)(D)是有向图D的k-彩虹控制数。用构造的方法得到有向图的k-彩虹控制数的一些上下界,这些界与图的顶点数、最大出度、罗马控制数等密切相关;给出γrk(D)=k的充分必要条件,利用概率方法得到了有向图的k-彩虹控制数的一个上界。

图的全局2-彩虹控制数的上界

计算图的全局彩虹控制数的精确值是一个NP完全问题,因此研究图的全局彩虹控制数的界具有重要的理论意义。本文对图的全局彩虹控制数的上界进行研究,通过构造法利用图的直径、围长和最小度等参数得到了直径至少为5或围长至少为6的图的全局2-彩虹控制数的上界。

全局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-彩虹控制数等于顶点数的所有图.