图与其导出子图的双罗马控制数的研究

摘要

令图G=(V,E)是简单连通图,V和E分别为图G的顶点集和边集。若函数f:V→{0,1,2,3}满足条件:i)对任意一点v∈V,若f(v)=0,存在v1,v2∈N(v),使得f(v1)=f(v2)=2,或存在ω∈N(v),使得f(ω)=3;ii) 对任意一点v∈V,若f(v)=1,存在ω∈N(v),使得f(ω)≥2,则称函数f为图G的双罗马控制函数。图G的双罗马控制函数的权值f(V)是图G中各点权值之和,图G的双罗马控制数是图G双罗马控制函数的最小权值,用γdR(G)表示。本文主要通过构造的方法证明了,对于任意的正整数a和b,都存在一类图G及其导出子图H,使得γdR(G)=a且γdR(H)=b。这个结果表明了一个图的双罗马控制数与其导出子图的双罗马控制数之间没有关系。