笛卡尔乘积有向图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)的精确值.

树的3-彩虹控制数的上界

对树的3-彩虹控制数进行研究,首先用构造法找到直径较小的树的3-彩虹控制数的上界.再通过分类讨论思想和数学归纳法得到一般的阶n大于等于5的树的3-彩虹控制数的上界.

全局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等的结果.

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

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

线型图和格图的3-彩虹控制数

对线型图和格图的3-彩虹控制数进行研究,通过归纳假设的思想给出线型图的3-彩虹控制数,用构造的方法找到格图的3-彩虹控制数的上界.

关于图的全局彩虹控制数

设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年)的一个错误结果.此外,还给出了一般图的全局彩虹控制数的上界.

网格图的2-彩虹控制数

给定一个图G和正整数k,图的彩虹控制函数f是满足下列条件的映射f:V(G)→2{1,2,…,k},使得对某个顶点v满足f(v)=,则∪u∈N(v)f(u)={1,2,…,k},其中V(G)是图G的顶点集,N(v)表示所有与v相邻的顶点的集合.彩虹控制函数f的权定义为w(f)=∑v∈V(G)|f(v)|.图的k-彩虹控制数γrk(G)是所有彩虹控制函数的权中的最小权.研究了2-彩虹控制函数的启发式算法的网格图的构造方法,实验结果表明,基于禁忌搜索策略的模拟退火算法比传统的模拟退火算法具有较好的效果.

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

图的全局2-彩虹控制的一个注记

为了研究树T的全局2-彩虹控制数γ_(gr2)(T)与2-彩虹控制数γ_(r2)(T)间的关系,分析了图的结构,采用分类讨论法和反证法,完全刻画了γ_(gr2)(T)=γ_(r2)(T)+1成立的直径等于5的所有树T,解决了Amjadi等人2017年未解决的问题。

树的彩虹控制数的一个多项式时间算法

设G是—个边染色图,G的彩虹子图是所有边都染不同颜色的子图.覆盖V(G)的不相交彩虹星的集合称为彩虹控制星集,图G最小彩虹控制星集的大小称为彩虹控制数,记为γ(G).本文给出了—个在边染色树T上寻找最小彩虹控制星集从而得到T的彩虹控制数的多项式时间算法.

双罗马控制数的界

为增强控制系统稳定性和精度,可以通过图论参数来界定图的双罗马控制数,以解决优化问题。文章首先利用双罗马控制数与控制数之间的关系,描述图中赋值为2的顶点个数满足的条件,并根据树的结构性质,给出树中叶子点和支撑点的一个赋值特点。其次引入图论参数,通过参数的概念及特性,得到双罗马控制数与最大度、生成树、3-彩虹控制有关的下界,同时给出双罗马控制数与最小覆盖数、打包数、意大利控制数有关的上界,建立双罗马控制数与图论参数之间联系,进一步表明双罗马控制在刻画图的性质中发挥着重要作用。