图的函数控制参数

论文摘要

在过去的三十年里,图论中发展最快的领域也许是图的“domination”的研究。根据实际背景的不同,现已定义的控制参数有几十种之多,而且随着研究的深入和应用的激发,新的参数如雨后春笋,不断涌现。 在本文中我们主要研究了以下两个部分:（1） 三正则无爪图的负控制数和符号控制数;（2） 图的罗马控制数。 第一章研究了三正则无爪图的负控制数和符号控制数,主要得到以下结果: 定理1.2.9 三正则无爪图的上负控制数Γ-（G）≤1/2|V（G）|。 推论1.2.10 若G是三正则无爪图,则Γ-（G）≤Γs（G）。 定理1.3.6 若G是连通的三正则无爪图,则γs（G）≤2/3n。 第二章研究了图的罗马控制数,主要得到以下结果: 定理2.3.1 若G是阶数为n的连通图,则γR（G）=γ（G）+κ当且仅当 （a） G中不存在点数为j的点集S（?）V使得对任意的1≤j≤κ-1,|N[S]|∈{n-（γ（G）+i）+2j∶j≤i≤κ-1}。 （b） 存在点集S0（?）V,1≤|S0|≤κ,使得|N[S0]|=n-（γ（G）+κ）+2|S0|。 推论2.3.2 若G是阶数为n的连通图,κ=min{l∶（?）S（?）V,1≤|S|≤l,|N[S]|-2|S|=n-（γ（G）+l）},则γR（G）=γ（G）+κ。 定理2.3.3 若T是阶数为n≥2的连通图,则γR（G）=γ（G）+3当且仅当（1）或（2）成立: （1） T=T1∪T2+v1v2,其中T1是健全的蜘蛛树,T2是病态的蜘蛛树,v1∈V（T1）,v2∈V（T2）,且T满足下列条件: （1a） 若T2是P2,则P2的任意顶点不能与T1的头相连。 （1b） v1与v2不全是脚点。

论文目录

• 引言
• 第一章 三正则无爪图的函数控制
• 1.1 基本概念
• 1.2 三正则无爪图的上负控制数
• 1.3 三正则无爪图的符号控制数
• 第二章 图的罗马控制数
• 2.1 基本概念
• 2.2 已知结果
• 2.3 主要结果与证明
• 参考文献
• 附录（1）: Terminology and Notation
• 附录（2）: 已完成文章
• 致谢