论文部分内容阅读
基于lan Stewart发表的一篇论文(Denfend the Roman Empire!,scien-tific American,Dec.1999,pp.136-138)的意图,M.A.Henning和S.T.Hedet-niemi[1]提出了防御罗马帝国的新策略,使最高统治着既节约了给养军团的花费又能防御罗马帝国.用图论的术语,设G=(V,E)是一个图,f:V→{0,1,2)是一个定义在图G的顶点集V上的函数,对f来说一个f(u)=0的顶点u被称为未防御点,如果它不与任何带正权的顶点相邻。函数f被称为弱罗马控制函数(简称WRDF),如果对每一个f(u)=0的顶点u,都与一个f(v)>0的顶点v相邻,并且函数f:V→{0,1,2}使得f(u)=1,f(v)=f(v)-1且f(w)=f(w),()w∈V-{u,v},没有未防御点。函数,的权w(f)=∑v∈Vf(V).图G的弱罗马控制函数的最小权称为弱罗马控制数,记为γT(G).在本文中,假定图T是由T1,T2通过增加一条新边而得到的一个新图,讨论由γr(T)与γr(T1)+γr(T2)之间的关系,并给出了γr(T)=γr(T1)+γr(T2)-1的充分必要条件,同时我们还讨论了连通度为1的图G去掉其一个割点后对其弱罗马控制数的影响。