正则图的Upper减控制数

论文摘要

图G=（V,E）上的函数f：V→{-1,0,1}被称为是图G上的一个减控制函数,如果对任意的点v∈V,都有减控制函数f是图G上的极小减控制函数,如果不存在减控制函数g：V→{-1,0,1},f≠g,使得对任意的点v∈V,g（v）≤f（v）都成立.图G的减控制数通常表示为γ-（G）,它为G上所有的减控制函数之中权重的最小数值；图G的Upper减控制数记为Γ-（G）,它是图G上所有的极小减控制函数之中权重的最大数值.也即是：γ-（G）=min{ω（f）|f为G上的减控制函数}和Γ-（G）=max{ω（f）|f为G上的极小减控制函数}.图G=（V,E）上的函数f：E→{-1,0,1}被称为是图G上的减边控制函数,如果对于图G的每一条边e∈E都有图G的减边控制数通常表示为γ’m（G）,它为图G上所有的减边控制函数之中权重的最小数值；图G的Upper减边控制数记为Γ’m（G）,它是图G上所有的极小减边控制函数之中权重的最大数值.也即是：γ-（G）=min{ω（f）|f为G上的减边控制函数}和Γ-（G）=max{ω（f）|f为G上的极小减边控制函数}.本文通过对图的结构性质的分析,得到了正则图的Upper减控制数,主要结论如下：（1）对任意的n阶三正则图G都有Γ-（G）≤5/8n,且此界是可达的,并构造出一类Γ-（G）=5/8n的图；对任意的n阶四正则图G都有Γ-（G）≤7/（10）n；对任意的n阶五正则图G都有Γ-（G）≤3/4n；（2）对任意的n阶k-正则图G都有Γ-（G）≤（2k-1）/（2（k+1））n；（3）对于任意的有m条边的三正则图G都有Γ’m（G）≤（2m）/3.

论文目录

• 摘要
• ABSTRACT
• 目录
• 1 绪论
• 1.1 基本概念
• 1.1.1 关于图的点控制的研究背景和一些概念
• 1.1.2 图的点控制数的研究背景
• 1.1.3 关于图的边控制的一些概念
• 1.2 研究概况
• 1.2.1 图的点控制数的研究概况
• 1.2.2 图的边控制数的研究概况
• 1.3 本文的主要结果
• 2 三、四、五正则图的Upper减控制数
• 2.1 引理
• 2.2 主要结果
• 3 k-正则图的Upper减控制数
• 4 三正则图的减边控制数
• 4.1 引理
• 4.2 主要结果
• 参考文献
• 在学期间的研究成果及发表的论文
• 致谢