图的弱罗马控制

论文摘要

基于Ian Stewart[11]发表的一篇论文（Defend the Roman Empirel，scientific Amer-ican，Dec．1999，pp．136-138）的意图，M．A．Henning和S．T．Hedetniemi[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}，没有未防御点．函数f的权记为w（f）=∑v∈Vf（v）．图G的弱罗马控制函数的最小权称为弱罗马控制数，记为γr（G）．在本文中，研究了图的不同控制数的一些理论性质，并且刻画了树T满足γr（T）=γ（T）的特征和图G满足γr（G）=γ（G）+1的特征，以及满足γr（G）=2γ（G）的图G的一些性质．

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 第二章 记号
• 第三章 相关的已知结果
• §3.1 图的罗马控制
• §3.2 图的弱罗马控制
• 第四章 主要结果与证明
• §4.1 弱罗马控制数的一些特殊值
• §4.2 弱罗马控制数的上下界
• Υ（T）=γ（T）'>§4.3 树T满足γ_Υ（T）=γ（T）
• Υ（G）=γ（G）+1'>§4.4 图G满足γ_Υ（G）=γ（G）+1
• Υ（G）=2_γ（G）'>§4.5 图G满足γ_Υ（G）=2_γ（G）
• 参考文献
• 致谢