论文部分内容阅读
设G=(V,E)是一个图,其中V=V(G)是图G的顶点集,E=E(G)是图G的边集.定义函数∫:V→ {0,1,2}满足以下条件:如果∫(v)=0,那么存在v的两个邻点v1,v2使得∫(v1)=∫(v2)=1,或存在v的一个邻点u使得∫(u)=2,称∫为G的一个罗马{2}-控制函数.记Vif为被∫赋值为i的点的集合.一个罗马{2}-控制函数的权重为f(V)=∑x∈Vf(v).称G的所有罗马{2}-控制函数中权重最小的函数的权重为图G的罗马{2}-控制数,记为γ{R2}(G).称G的一个具有权重γ{R2}(G)的罗马{2}-控制函数为G的一个γ{R2}-函数.如果函数f是G的一个罗马{2}-控制函数并且还满足V1f∪V2f是一个独立集,则称f是G的一个独立罗马{2}-控制函数.本文给出了 γ{R2}(M(G))和γ{R2}(G)之间的关系,其中M(G)是图G的Mycielskian图.对于任意给定的两个正整数a,b,其中a ≥ 2,b ≥ 2,我们构造了一个图G以及G的一个导出子图H使得γ{R2}(G)=a且γ{R2}(H)=b.并且,我们研究了在一个图上加一条边对这个图的罗马{2}-控制数的影响;在独立罗马{2}-控制方面,我们给出了真区间图的独立罗马{2}-控制数的一个上下界,以及计算带有限制的单圈图的独立罗马{2}-控制数的线性时间算法.如果函数f:V→ {0,1,2,3}满足以下条件:(1)如果∫(v)=0,那么存在u的两个邻点v1,v2使得∫(v1)=∫(v2)=2,或存在v的一个邻点u使得∫(u)=3,(2)如果∫(v)=1,那么存在v的一个邻点u使得∫(u)=2或3,那么就称∫为G的一个双罗马控制函数.类似于G的罗马{2}-控制的相关定义,有G的独立罗马{2}-控制和双罗马控制的相关定义.在双罗马控制方面,我们讨论了在一条路的最小双罗马控制函数的唯一性.